描述
將正整數n 表示成一系列正整數之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。
正整數n 的這種表示稱為正整數n 的劃分。

輸入
標準的輸入包含若干組測試數據。每組測試數據是一行輸入數據,包括兩個整數N 和 K。
(0 < N <= 50, 0 < K <= N)
輸出
對于每組測試數據，輸出以下三行數據:
第一行: N劃分成K個正整數之和的劃分數目
第二行: N劃分成若干個不同正整數之和的劃分數目
第三行: N劃分成若干個奇正整數之和的劃分數目
樣例輸入
5 2
樣例輸出
2
3
3

分析
第二行：求若干個不相同的正整數之間的劃分，狀態及狀態轉移類似（唯一區別選j后剩余可選數字變成1 到 (j - 1)）簡單整數劃分，利用狀態d[i][j]表示從1-j中若干個數湊i，且每個數無限取。遞推時注意邊界處的狀態轉移方程，當i == j時，d[i][j] = d[i][j - 1] + 1。
第一行：劃分為k個整數，使用狀態d[i][j]表示將i劃分為j個整數，轉移方式分為選取1的劃分數目： d[i - 1][j - 1]（選1后，總數自然要減1，劃分的個數也少1）和不選取1的劃分數目：d[i - j][j]（不選1，意味著每個位置上的數都要大于1，首先j個位置每個位置都至少為1，總數減少j，然后將i - j繼續在j個位置劃分），最后兩者相加即可，注意邊界，當i == j時，d[i][j] = 1（或者直接初始化dk[0][0] = 1，慢一些）。
第三行：劃分為若干個奇數，借用上面的思想，使用狀態dodd[i][j]表示將i劃分為j個奇數，deven[i][j]表示將i劃分為若干個偶數。狀態轉移同樣分為選
1的個數：對于奇數，選1后，剩余數值i - 1，劃分為j - 1個奇數，對于偶數，不能選1。不選1的個數：對于奇數，同上，將1鋪好后，只能選j個偶數，對于偶數反之。邊界為deven[0][0] = 1，dodd[0][0] = 1（當然可以使用上面那種初始化方法，就是稍微繁瑣一些，但是更快）。

#include<iostream> #include<cstring> using namespace std; const int MAX = 55; int dk[MAX][MAX]; int dd[MAX][MAX]; int dod[MAX][MAX],dev[MAX][MAX]; int main(){ int n,k,i,j;while(scanf("%d%d",&n,&k) != EOF){memset(dk,0,sizeof(dk));memset(dd,0,sizeof(dd));memset(dev,0,sizeof(dev)); memset(dod,0,sizeof(dod));dod[0][0] = 1;dev[0][0] = 1;for(i = 1;i <= n; ++i){for(j = 1;j <= i; ++j){if(i == j){dd[i][j] = dd[i][j - 1] + 1;dk[i][j] = 1;}else{dd[i][j] = dd[i][j - 1] + dd[i - j][min(i - j,j - 1)];dk[i][j] = dk[i - j][j] + dk[i - 1][j - 1];} dev[i][j] = dod[i - j][j];dod[i][j] = dev[i - j][j] + dod[i - 1][j - 1];}}int sum = 0;for(i = 0;i <= n; ++i)sum += dod[n][i];printf("%d\n%d\n%d\n",dk[n][k],dd[n][n],sum);}return 0; }

總結

以上是生活随笔為你收集整理的百练#4119复杂的整数划分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。