AcWing 1023. 买书-经典完全背包问题
原题链接
简单
作者:
rushhhhh
,
2021-02-15 11:27:41
,
所有人可见
,
阅读 273
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int f[N];
/*
状态表示f[i][j]
集合:在前i种货币中选,花完j元去买书,有几种买书方案的集合
属性:count,方案数
状态计算:
f[i-1][j-v*k],选k个第i种货币(k从0到最大)
其中,
f[i,j] = f[i-1,j]+f[i-1,j-1v]+f[i-1,j-2v]+...+f[i-1,j-kv]
f[i,j-v] = f[i-1,j-1v]+f[i-1,j-2v]+...+f[i-1,j-kv]
所以,
f[i,j] = f[i-1,j] + f[i,j-v]
*/
int main()
{
cin >> n;
f[0] = 1;
int v[5] = {10,20,50,100};
for(int i=0; i<=3; i++)
for(int j=v[i]; j<=n; j++)
f[j] = f[j] + f[j-v[i]];
cout << f[n];
return 0;
}