HDu 1028(整数分割問題)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1028
 
せいすうぶんかつもんだい
整数区分-古い成長談の問題:
説明
整数分割は古典的な問題です.次の要件を完了するためにプログラムを書いてください.
 
 
入力
各入力セットは2つの整数nとkである.(1 <= n <= 50, 1 <= k <= n)
しゅつりょく
入力されたn,kについて;
1行目:nをいくつかの正の整数の和に分割する分割数.
2行目:nをk個の正の整数の和に分割する分割数.
3行目:nを最大数kを超えない分割数に分割する.
4行目:nをいくつかの奇正整数の和に分割する分割数.
5行目:nをいくつかの異なる整数の和に分割する分割数.6行目:空の行を印刷
サンプル入力

5 2

サンプル出力

7

2

3

3

3

ヒント
サンプル出力プロンプト:
1.5をいくつかの正の整数の和に分割する.5、4+1、3+2、3+1+1、2+2+1、2+1+1、1+1+1+1
2.5を2つの正の整数の和に分けたもの:3+2,4+1
3.5を最大数が2を超えないように分割する:1+1+1+1,1+1+2,1+2+2
4.5をいくつかの奇正整数の和に分割する:5,1+1+3,1+1+1+1
5.5をいくつかの異なる整数の和に分割する:5,1+4,2+3
 
 
分析:
 
この問題はダイナミックプランニング(Dynamic Programming)メソッドを使用して解決します.
nをいくつかの正の整数の和に分割する分割数を求める
 
1.分割された複数の整数が同一である場合
dp[i][j]をiをj以下に分割する分割数とする
(1)i(2)i>jの場合,分割にjが含まれているか否かによって2つに分けることができる.区分にjが含まれている場合、区分案数はdp[i-j][j]である.分割数にjが含まれていない場合は、iをj−1以下に分割する分割数に相当し、dp[i][j−1]となる.したがって、i>jの場合、dp[i][j]=dp[i-j][j]+dp[i][j-1];
(3)i=jの場合、分割にjが1つしか含まれていない場合、分割にjが含まれていない場合は、iをj-1以下に分割する分割数に相当する.このときdp[i][j]=1+dp[i][j-1]となる.
dp[n][n]は問題1を解決することができ、dp[n][k]はnを最大数kを超えない分割数に分割し、問題3を解決することができることを示す.
 
2.分割された正の整数が異なる必要がある場合
dp[i][j]をiをjを超えない異なる整数に分割する分割数とする
(1)i(2)i>jの場合,分割にjが含まれているか否かによって2つに分けることができる.区分にjが含まれている場合、残りの区分の最大はj-1であり、シナリオ数はdp[i-j][j-1]である.分割にjが含まれていない場合は、iをj−1以下に分割する分割数に相当し、dp[i][j−1]となる.したがって、i>jの場合、dp[i][j]=dp[i-j][j-1]+dp[i][j-1];
(3)i=jの場合、分割にjが1つしか含まれていない場合、分割にjが含まれていない場合は、iをj-1以下に分割する分割数に相当する.このときdp[i][j]=1+dp[i][j-1]
 
dp[n][n]は、nを異なる整数に分割する分割数を表し、問題を解決することができる.
 
二nをk個の整数に分割する分割数
dp[i][j]をiをj個の整数に分割する分割数とする.
(1)i(2)i=jの場合、iはi個1の和に分けることができ、dp[i][j]=1;
(3)i>jであれば、分割数に1が含まれているかどうかによって2種類に分けることができる:分割数に1が含まれている場合は、「エッジカット法」を用いてj個の分割をそれぞれ1つ切り取り、問題をi-jのj-1個の分割数に変換し、dp[i-j][j-1]とすることができる.分割に1が含まれていない場合は、「エッジカット法」を用いてj個の分割数の一番下の数を切り取り、題目をi-jを求めるj個の分割数に変換し、dp[i-j][j]とする.したがってi>jではdp[i][j]=dp[i-j][j-1]+dp[i-j][j]となる.
 
dp[n][k]は、nをk個の整数に分割する分割数であり、問題2を解決することができる.
 
 
三nをいくつかの正奇数の和に分ける区分数
 
f[i][j]はiをj個の奇数の和に分割する分割数、g[i][j]はiをj個の偶数の和に分割する分割数とする.
エッジカット法を用いてg[i][j]のj個の区分をすべて1削除し,f[i-j][j]を得ることができるので,
g[i][j] = f[i-j][j].
f[i][j]には1を含む分割スキームと1を含まない分割スキームがある.1を含む分割スキームについては、1の分割を除去し、「i−1をj−1個の奇数の和に分割する分割数」、すなわちf[i−1][j−1]に変換することができる.1を含まない分割スキームでは、エッジカット法を用いてj個の分割ごとに1を削除し、「i−jをj個の偶数の和に分割する分割数」、すなわちg[i−j][j]に変換することができる.
だからf[i][j]=f[i-1][j-1]+g[i-j][j]です.
f[n][0]+f[n][1]+......+f[n][n]はnをいくつかの奇数に分割する分割数であり,問題4の答えである.
 
回転元:http://www.cnblogs.com/wanghetao/archive/2013/11/25/3442192.html
 
この問題はまさに問題1です.

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

#include <cstdlib>

#include <vector>

#include <set>

#include <map>

#define LL long long

using namespace std;

int dp[200][200];

int main()

{

    int n;

    for(int i=1;i<=120;i++)

        for(int j=1;j<=120;j++)

        {

            if(i<j)dp[i][j]=dp[i][i];

            else if(i==j)dp[i][j]=1+dp[i][j-1];

            else dp[i][j]=dp[i][j-1]+dp[i-j][j];

        }

    while(scanf("%d",&n)>0)

    {

        printf("%d
",dp[n][n]);

    }

}

View Code