using namespace std;
int sum=0;
void dfs(int n,int m)
{
if(n==0) sum++;
else if(n<0) return;
else{
for(int i=m;i>=1;i--){
dfs(n-i,i-1);
}
}
}
int main()
{
int t;cin>>t;
for(int i=0;i<t;i++){
sum=0;
int n,m;cin>>n>>m;
printf("case #%d:\n",i);
dfs(n,m);
cout<<sum<<endl;
}
}
没想到01背包，直接手动搞得其他方法。我的想法应该还是十分麻烦的。首先f(x,y)表示x不大于y的拆分，则f(x,y)可以分解成为f(x,y-1)+最大拆分为y的个数。最大拆分为y的个数可以表示为f(x-y,y-1)，然后动态规划就可以了。
附C代码：
#include <stdio.h>
int main()
{
int ans[51][21], i, j, k, x, ma;
for(i=0; i<51; i++) for(j=0; j<21; j++) ans[i][j]=0;
for(i=1; i<51; i++)
{
if(i>20) ma=20;
else ma=i;
for(j=1; j<=ma; j++)
{
x=i;
if(j) ans[i][j]+=ans[i][j-1];
if(i<21 && j==i) {ans[i][j]++; break;}
k=j;
x-=k--;
if(x>19)
{
while(x-k<k)
{
ans[i][j]+=ans[x-k][k];
k--;
}
}
ans[i][j]+=ans[x][k];
}
if(ma<20) for(j=ma; j<21; j++) ans[i][j]=ans[i][ma];
}
int T, I, n, m;
scanf("%d",&T);
for(I=0; I<T; I++)
{
scanf("%d %d",&n,&m);
printf("case #%d:\n%d\n",I,ans[n][m]);
}
return 0;
}
using namespace std;
int n,m;
int ans=0;
void dfs(int i,int sum)
{
if(sum==n)
{
ans++;
return;
}
if(i>m||sum>n)
return;
dfs(i+1,sum+i);
dfs(i+1,sum);
}
int main()
{
int t;
cin>>t;
for(int i = 0; i < t; i++)
{
cin>>n>>m;
ans=0;
dfs(1,0);
printf(“case #%d:\n”,i);
cout<<ans<<endl;
}
return 0;
}
设 $dp(i, j)$ 表示用 1..=i 闭区间里的不重复正整数表示 $j$ 的方案数。一般情况下有两种选法：使用零数 $i$，然后用前 $i-1$ 个数字组成 $j-i$；或不使用零数 $i$，使用前 $i-1$ 个数字组成 $j$。这样得到了
$$
dp(i, j)=dp(i-1,j)+dp(i-1,j-i),j\ge i
$$
$$
dp(i,j)=dp(i-1,j),j<i
$$
（我没能捉摸明白 EOJ 的 cases 怎么用所以只能这样写 Math 公式了）
这样看来这其实就是一个背包问题。时间复杂度是 $O(\sum_{i=1}^tn_im_i)$。
#include "bits/stdc++.h"
using namespace std;
using u64 = uint64_t;
int main() {
u64 t;
cin >> t;
for (u64 query = 0; query < t; ++query) {
cout << "case #" << query << ":\n";
u64 n, m;
cin >> n >> m;
vector<u64> dp(n + 1, 0);
dp[0] = 1;
for (u64 i = 1; i <= m; ++i) {
for (u64 j = n; j >= i; --j) {
dp[j] += dp[j - i];
}
}
cout << dp[n] << '\n';
}
}
应该有简单的方法，不过我用的是01背包
using namespace std;
int T,n,m;
int dp[60];
void solve()
{
cin>>n>>m;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i<=m;i++)
for(int j=n;j>=i;j–)
dp[j]+=dp[j-i];
cout<<dp[n]<<endl;
}
int main()
{
scanf(“%d”,&T);
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}
for(int j=n;j>=i;j–)注意这层循环是倒着枚举的，否则这个数就可以取多遍了
记得有一题，是把一个数分解成2的幂加起来，方法也类似，题号记不得了，但就是EOJ上的题
不知道为什么，不压减空间居然有问题了