AcWing 3428. 放苹果
原题链接
简单
作者:
吃饭不回家
,
2024-03-13 17:54:02
,
所有人可见
,
阅读 7
放苹果(动态规划求解)
#include<bits/stdc++.h>
using namespace std;
const int N=12;
int n,m;
int f[N][N];
//参考:900、整数划分
//f[i][j]表示总和为i,恰好被划分为j个数相加
//则根据划分的数最小值为多少可以分为两类:1.最小值为1;2.最小值大于1
//转移方程:f[i][j]=f[i-1][j-1]+f[i-j][j];
//最终结果就是总和为M(苹果数),被划分为0~N个数相加(如此将盘子中放0个苹果的情况也考虑进去了)
int main()
{
while(cin>>m>>n)
{
memset(f,0,sizeof f);
f[0][0]=1;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=i && j<=n;j++)
{
f[i][j]=f[i-1][j-1]+f[i-j][j];
}
}
int res=0;
for(int i=1;i<=n;i++) res+=f[m][i];
cout<<res<<endl;
}
return 0;
}