买书

完全背包问题 + 方案数

闫式DP分析法：

1.$f[i,j]$的含义是什么？
$f[i,j]$为挑选到第i本数时，开销为j的最大方案数

2.$f[i,j]$怎么转移？
(1)如果不挑选第i个物品，那么其方案数等于$f[i-1,j]$
(2)如果从第i个物品中挑选，那么其方案书等于$f[i-1,j-v[i]]$

综上所述，递推关系为：$f[i,j] = f[i-1,j] + f[i-1,j-v[i]]$

解题代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
int v[5] = {0,10,20,50,100};
int d[N];

int main()
{
    scanf("%d", &n);
    d[0] = 1;
    for(int i = 1; i <= 4; i ++ )
    {
        for(int j = v[i]; j <= n; j ++ )
            d[j] += d[j-v[i]];
    }
    printf("%d", d[n]);
    return 0;
}