CodeVS/1039

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
数的划分	★★☆☆☆	答案正确	100	2015-2-2 17:20:08	无

题意

n个数划分成m份，其中(1,1,2)(2,1,1)(1,2,1)算作一种分法，问分法总数。

题解

• 写起来简单想起来头都大了。主要是分类。f[i][j]表示i分成j份的分法，可以分为有1的和没有1的来求和，有1的数量等同于f[i-1][j-1]（相当于多分了一组1），没有1的数量等同于f[i-j][j]（相当于所有分法底上垫上1），于是得到方程：

f[i][j]=f[i-j][j]+f[i-1][j-1];

代码

1039.cpp代码已折叠 展开折叠内容
#include<iostream> using namespace std; int m,n,f[300][300]; int main() { cin>>m>>n; f[0][0]=1; for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) if(i>j) f[i][j]=f[i-j][j]+f[i-1][j-1]; else f[i][j]=f[i-1][j-1]; cout<<f[m][n]; return 0; }