二刷提高课,题解目录在这里— 提高课的题解目录
注意这里有个条件就是必须用满所拥有的钱
所以就变成了无限物品恰好装满N的方案数了
所以就是个完全背包简化版
#include<iostream>
using namespace std;
int f[10][1010];
int a[5]={0,10,20,50,100};
int main(){
int n;
cin>>n;
f[0][0]=1;
for(int i=1;i<=4;i++)
for(int j=0;j<=n;j++)
{
f[i][j]=f[i-1][j];
if(j>=a[i])f[i][j]+=f[i][j-a[i]];//完全背包的优化
}
cout<<f[4][n];
}
感谢佬给我的思路