$\LARGE\color{orange}{刷题日记(算法提高课)}$

这道题是完全背包问题求方案数，我们给出 $f[i][j]$ 所表示的集合：所有考虑前 $i$ 个物品，总体积恰好为 $j$ 的不同选择，属性为选择的总和，即方案数

对于不选第 $i$ 个物品，有：$f[i][j]=f[i-1][j]$

对于选第 $i$ 个物品，有：$f[i][j]=f[i-1][j-v]+f[i-1][j-2v]+f[i-1][j-3v]+\dots +f[i-1][j-sv]$

整体就是 $f[i][j]=f[i-1][j]+f[i-1][j-v]+f[i-1][j-2v]+f[i-1][j-3v]+\dots +f[i-1][j-sv]$

与一般完全背包不同的是，求方案数是将前面所有的状态加起来

往后写一位，有：$f[i][j-v]=f[i-1][j-v]+f[i-1][j-2v]+f[i-1][j-3v]+\dots +f[i-1][j-sv]$

即 $f[i][j]=f[i-1][j]+f[i][j-v]$

这里的 $v$ 指的是体积，本题中指的是书的价格

完整代码：

#include <iostream>

using namespace std;

const int N = 1010;
int f[N]; 
int v[5] = {0, 10, 20, 50, 100};

int n;

int main()
{
    cin >> n;
    f[0] = 1;//对于这种恰好的定义，一定要记得初始化
    for(int i = 1; i <= 4; i++)
        for(int j = v[i]; j <= n; j++)
            f[j] = f[j] + f[j - v[i]];
    cout << f[n] << endl;
    return 0;
}