比较简单的数学题。
先设状态,以分解出的个数 \(m\) 划分阶段,以数 \(n\) 划分子问题。
则显然的,有 \(f_{i,j}=\sum\limits_{0\le w \le j} f_{i-1,j-w}\)。
这个式子啥意思呢,这个阶段的结果由上一个阶段转移而来,\(w\) 是最后一个划分出的数,\(i\) 就是数的个数。
接下来考虑初始化。显然把一个数 \(n\) 划分成一个数是只有一种方案的,即 \(f_{1,i}=1\)。
然后快乐的通过了。
#include <stdio.h>
int n,k,i,j,w;
int f[105][105];
const int mod=1000000;
int main()
{
for(i=0;i<=100;++i)
f[1][i]=1;
for(i=2;i<=100;++i)
for(j=0;j<=100;++j)
for(w=0;w<=j;++w)
(f[i][j]+=f[i-1][j-w])%=mod;
while(~scanf("%d %d",&n,&k)&&n&&k)
{
printf("%d\n",f[k][n]);
}
return 0;
}
标签:do,le,How,int,划分,UVA10943,add
From: https://www.cnblogs.com/Syara/p/17092878.html