Standard IO-----数的划分问题（一）（CCF 1185）

数的划分问题（一）

题目描述 把正整数N分解成M个正整数的和，即使M个数相同但顺序不同也认为是不同的方案，要求总方案数。如3=1+2跟3=2+1是两个不同的方案。

输入 第一行包含两个整数N和M(1<=M<=N<=50)。

输出 输出一个数表示方案数。

样例输入

3 2

样例输出

2

数据范围限制

1<=M<=N<=50

做题地址：CCF中学生程序设计在线评测系统-1185. 数的划分问题（一）（需要注册）

---

作为一道DP，首先要用搜索的眼光去看：

题目已经说明：

方案数可以重复 最小值为1 m不会大于n

可以使用深搜，把拆分的每一个数的每一种情况进行枚举，统计方案。

1<=M<=N<=50

应该不会TLE吧……

#include<cstdio> #include<algorithm> #include<iostream> using namespace std; int n,m,tot; void dfs(int t,int sum) { if(t==m && sum==0) { tot++; return ; } if(t>m || sum<0) return ; for(int i=1;i<=sum;i++) dfs(t+1,sum-i); } int main() { scanf("%d %d",&n,&m); dfs(0,n); printf("%d\n",tot); } /* 结果：时间超限 运行时间：132 ms 运行空间：296 KB 代码长度：305 bytes */

---

记忆化搜索？ 把每个n，m对应的答案存在数组里，需要时直接使用

递归式？ 猜猜看，哪个是正确的递归式

1：

if(f[n1][m1]) return f[n1][m1]; if(n1==m1) return f[n1][m1]=1; if(m1==1) return f[n1][m1]=1; if(m1>2) return F(n1,m1-1)+F(n1-1,m1)-1; return F(n1,m1-1)+F(n1-1,m1);

2：

if(m1==1 || n1==m1) return 1; if(n<1) return 0; if(f[n1][m1]) return f[n1][m1]; int s=0,t=n1-m1+1; for(int i=1;i<=t;i++) s+=F(n1-i,m1-1); return f[n1][m1]=s;

是1，还是2？

都不对 O(∩_∩)O~（恭喜你被耍了）

正确的递归式:

if(m1==1 || n1==m1) return 1; if(n<1) return 0; if(f[n1][m1]) return f[n1][m1]; long long s=0; int t=n1-m1+1; for(int i=1;i<=t;i++) s+=F(n1-i,m1-1); return f[n1][m1]=s;

鉴于此题数据过大，储存方案需用long long int

1<=M<=N<=50(过大的数据)

正确的记忆化搜索

#include<cstdio> #include<algorithm> #include<iostream> using namespace std; long long n,m,f[55][55]; long long int F(long long int n1,long long int m1) { if(m1==1 || n1==m1) return 1; if(n<1) return 0; if(f[n1][m1]) return f[n1][m1]; long long s=0,t=n1-m1+1; for(int i=1;i<=t;i++) s+=F(n1-i,m1-1); return f[n1][m1]=s; } int main() { //freopen("out.txt","w",stdout); scanf("%lld %lld",&n,&m); printf("%lld\n",F(n,m)); } /* 结果：评测通过 运行时间：0 ms 运行空间：316 KB 代码长度：432 bytes */

---

DP在此

这里的DP就是根据边界得到的初始数据，一步一步推出来的（怎么感觉像递推O(∩_∩)O~）

有两种边界处理方法（两种初始化方法）

1:

#include<cstdio> #include<algorithm> #include<iostream> using namespace std; int n,m; long long f[55][55]; int main() { //freopen("out.txt","w",stdout); scanf("%d %d",&n,&m); for(int i=1;i<=50;i++) f[i][i]=f[i][1]=1; for(int j=1;j<=m;j++) for(int i=1;i<=n;i++) if(!f[i][j]) for(int k=1;k<=i;k++) f[i][j]+=f[i-k][j-1]; printf("%lld\n",f[n][m]); }

2:

#include<cstdio> #include<algorithm> #include<iostream> using namespace std; int n,m; long long f[55][55]; int main() { //freopen("out.txt","w",stdout); scanf("%d %d",&n,&m); f[0][0]=1; for(int j=1;j<=m;j++) for(int i=1;i<=n;i++) for(int k=1;k<=i;k++) f[i][j]+=f[i-k][j-1]; printf("%lld\n",f[n][m]); }

差别自己找

---

IN THE END

如果把DP中初始化后的数组打印出来：

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 ……

这不是杨辉三角么？（( ⊙ o ⊙ )啊！）