整数划分
时间限制:3000 ms | 内存限制:65535 KB
难度:3
- 描述
- 将正整数n表示成一系列正整数之和:n=n1+n2+…+nk,
其中n1≥n2≥…≥nk≥1,k≥1。
正整数n的这种表示称为正整数n的划分。求正整数n的不
同划分个数。
例如正整数6有如下11种不同的划分:
6;
5+1;
4+2,4+1+1;
3+3,3+2+1,3+1+1+1;
2+2+2,2+2+1+1,2+1+1+1+1;
1+1+1+1+1+1。- 输入
- 第一行是测试数据的数目M(1<=M<=10)。以下每行均包含一个整数n(1<=n<=10)。
- 输出
- 输出每组测试数据有多少种分法。
- 样例输入
-
1 6
- 样例输出
-
11
思路:动态规划:我们用q[n][m]表示整数n (零数不超过m)的划分数。
①当n = m 时,q[n][n]=q[n][n-1]+1;
②当n < m 时,q[n][m]=q[n][n];
③当n > m 时, q[n][m]=q[n][m-1]+q[n-m][m];
代码如下:(递推版)
#include <iostream> #include <string> #include <cstdio> #include <algorithm> using namespace std; #define n 11 int main() { int q[n+1][n+1]; int i,j; for(i=1;i<=n;i++) q[i][1]=q[1][i]=1; for(i=2;i<=n;i++) for(j=2;j<=n;j++) { if(i==j) q[i][i]=q[i][i-1]+1; else if(i<j) q[i][j]=q[i][i]; else q[i][j]=q[i][j-1]+q[i-j][j]; } int m,T; cin>>T; while(T--) { cin>>m; cout<<q[m][m]<<endl; } return 0; }
(递归版)
#include <iostream> #include <string> #include <cstdio> #include <algorithm> using namespace std; int fac(int n,int m) { if(n==1||m==1)return 1; if(n==m)return 1+fac(n,n-1); if(n>m) return fac(n,m-1)+fac(n-m,m); return fac(n,n);//n<m } int main() { int n,T; cin>>T; while(T--) { cin>>n; cout<<fac(n,n)<<endl; } return 0; }
第二种解法:
按照楼下weiwei2012start 的说法:研究了一下:这个整数划分其实就是一个多重背包问题。
具体解法如下:
一个数n可以看成背包容量为n的背包,f[n]由n个价值和花费分别为i 的物品,能装满背包的种类数,而每种物品的数量不限,正好是一个完全背包问题。
int f[1000]; memset(f,0,sizeof(f)); f[0]=1;//注意这里很重要 for(int i=1; i<=n; i++) for(int j=i; j<=n; j++) f[j]=f[j]+f[j-i];
这下大大提高了效率。
f[121]=2056148051;
f[500]=2300165032574323995027;