「2019-08-13 省常中互测」找钱

Description

现在给你$n$种面值,每种面值我们自己手中有$b_i$张,售货员手中有$c_i$张。

问有多少种情况可以买下$X$元的物品。

Data Range

$n\leq 1000, m\leq 100000$。

Solution

对于每一人我们做一次完全背包。

然后发现对于每一个面值是递增的,然后可以用前缀和优化背包。

最后统计一下答案就可以了。

Code

#include <bits/stdc++.h>

using namespace std;

const int P = 1e9 + 7;

int n, m;
int f[1005][10005];
int g[1005][20005];
int a[1005], b[1005], c[1005];

template <typename T> void pls(T &x, T y) {
    x += y;
    if (x >= P) x -= P;
}

template <typename T> T mul(T x, T y) {
    return (long long) x * y % P;
}

int main() {
    freopen("deal.in", "r", stdin);
    freopen("deal.out", "w", stdout);
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i] >> c[i] >> b[i];
    }
    f[0][0] = 1;
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= a[i] - 1; j ++) {
            int sum = 0;
            for (int k = 0; j + a[i] * k <= m; k ++) {
                pls(sum, f[i - 1][j + a[i] * k]);
                if (k > b[i]) pls(sum, P - f[i - 1][j + a[i] * (k - b[i] - 1)]); 
                f[i][j + a[i] * k] = sum;
            }
        }
    }
    g[n + 1][0] = 1; 
    for (int i = n; i >= 1; i --) {
        for (int j = 0; j <= a[i] - 1; j ++) {
            int sum = 0;
            for (int k = 0; j + a[i] * k <= m * 2; k ++) {
                pls(sum, g[i + 1][j + a[i] * k]); 
                if (k > c[i]) pls(sum, P - g[i + 1][j + a[i] * (k - c[i] - 1)]); 
                g[i][j + a[i] * k] = sum;
            }
        }
    }
    int ans = 0; 
    for (int i = 0; i <= m; i ++) {
        int tmp = 0;
        for (int j = 1; j <= n; j ++) {
            if (a[j] > i) {
                tmp = j;
                break;
            }
        }
        if (tmp) {
            pls(ans, mul(f[n][i], g[tmp][i + m])); 
        }
    }
    cout << ans << endl;
    return 0; 
}
最后修改:2019 年 08 月 24 日 08 : 54 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论