这是一道典型的整数划分题目，适合正在研究动态规划的同学练练手，但是和上一个随笔一样，我是在Coursera中评测通过的，没有找到适合的OJ有这一道题(找到的ACMer拜托告诉一声~)，这道题考察得较全面，考察了三种整数划分的变形问题。
Openjudge 原题网址：Bailian2014研究生推免上机考试（校内）
原题：
- Description
-
将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。
正整数n 的这种表示称为正整数n 的划分。 - Input
- 标准的输入包含若干组测试数据。每组测试数据是一行输入数据,包括两个整数N 和 K。
(0 < N <= 50, 0 < K <= N) - Output
- 对于每组测试数据，输出以下三行数据:
第一行: N划分成K个正整数之和的划分数目
第二行: N划分成若干个不同正整数之和的划分数目
第三行: N划分成若干个奇正整数之和的划分数目 - Sample Input
-
5 2
- Sample Output
-
2
3
3 - Hint
- 第一行: 4+1, 3+2,
第二行: 5，4+1，3+2
第三行: 5，1+1+3， 1+1+1+1+1+1
有关这三种变形问题的具体解释在我的另一篇随笔中有提及：整数划分问题-解法汇总，看不懂Code的ACMer见这篇随笔。
Code如下：
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; #define MAX 51 int dp1[MAX][MAX];
int dp2[MAX][MAX];
int dp3[MAX][MAX]; /*划分成K个整数*/
void DP1()
{
for (int n = ; n < MAX; n++)
{
for (int k = ; k < MAX; k++)
{
if (n == k || k == )
dp1[n][k] = ;
else if (n > k)
dp1[n][k] = dp1[n - k][k] + dp1[n - ][k - ]; //划分中不包含1 + 划分中至少有一个1
}
}
} /*划分成<=m的不同整数*/
void DP2()
{
for (int n = ; n < MAX; n++)
{
for (int m = ; m < MAX; m++)
{
if (n > m) //除m外的数不包括m(即剩下划分总和为n-m中没有m)
dp2[n][m] = dp2[n - m][m - ] + dp2[n][m - ];
else if (n < m)
dp2[n][m] = dp2[n][n];
else
dp2[n][m] = + dp2[n][m - ];
}
}
} /*划分成<=m的奇正整数*/
void DP3()
{
for (int n = ; n < MAX; n++) //+1不会增加种类
{
for (int m = ; m < MAX; m+=)
{
if (n > m)
dp3[n][m] = dp3[n - m][m] + dp3[n][m - ];
else if (n < m)
dp3[n][m] = dp3[n][n];
else
dp3[n][m] = + dp3[n][m - ];
dp3[n][m + ] = dp3[n][m];
}
}
} int main()
{
DP1();
DP2();
DP3();
int num, k;
while (scanf("%d%d", &num, &k) != EOF)
{
printf("%d\n", dp1[num][k]);
printf("%d\n", dp2[num][num]);
printf("%d\n", dp3[num][num]);
} return ;
}
小墨-原创