P2834 题解

· · 题解

题意

本题题目描述简短，不多赘述。

思路

由于是组合计数问题，需要考虑到纸币种类这个阶段以及每次加入一种新纸币产生的贡献。

所以使用状态 f_{i,j} 表示只用前 i 种纸币凑到金额 j 的方案数。

于是有以下两种情况：

  1. 用了若干张 a_i，此时前继状态为 f_{i,j-a_i},由此转移即可。

  2. 没有用一张 a_i，直接 f_{i-1,j} 转移即可。

注意：需要初始化边界条件 f_{i,0} \gets 1。

贴出代码为：

for(int i = 1; i<=n; i++) {
    for(int j = 0; j <= w; j++) {
        if(j < a[i]) {
            f[i][j] = f[i-1][j];
        }
        else {
            f[i][j] = f[i][j-a[i]] + f[i-1][j];
            f[i][j] %= mod;
        }
    }
}

时间复杂度为 O(nw)，空间复杂度为 O(nw)，足以通过此题。

但是空间还可以再做优化，观察到 f 的第一维 i 只与 i-1 有关，这样的转移是不必要的，直接去掉即可。

完整代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5;
const int W = 1e4 + 5;
const int inf = 2e9;
const int mod = 1e9 + 7;
int n,w;
int a[N];
int f[W];

int main() {
    cin>>n>>w;
    for(int i = 1; i<=n; i++) {
        cin>>a[i];
    }
    f[0] = 1; //边界
    for(int i = 1; i<=n;i++) {
        for(int j = a[i]; j<=w; j++) {
            f[j] += f[j - a[i]] % mod;
            f[j] %= mod;
        }
    }
    cout<<f[w]<<endl;
    return 0;
}