幸亏这道题数据小,用了四重循环过了
f [某位] [有多少能量] [能量总共多少] 的情况数
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int m,n; //m量 给 n个 10
int f[11][11][11];// f [某位] [有多少能量] [能量总共多少] 的情况数
int main()
{
int t; cin>>t;
while(t--)
{
cin>>m>>n;
memset(f,0,sizeof f); //别忘了初始化
for(int i=0;i<=m;i++)
f[1][i][i]=1;
for(int i=2;i<=n;i++)
for(int s=0;s<=m;s++) //该位的能量
for(int e=0;e<=s;e++) //上一位的能量 <=s
for(int sum=0;sum<=m;sum++) //上一位的总共能量
if(sum+s<=m) //如果加上s在能量范围内就行
f[i][s][sum+s]+=f[i-1][e][sum];
int ans=0;
for(int i=0;i<=m;i++)
ans+=f[n][i][m];
cout<<ans<<endl;
}
}
不过那个二重循环的做法感觉有点难想
f[i,j]的方案数由两种情况组成:
最小值是0的:相当于上一位的方案数(比如上一位是1 2 3 ,现在是01, 02 , 03)
最小值不是0:加上f[i-j][j] (比如原来是 用i-j的能量分给j个人 , 现在直接把原来的方案每个人+1能量)