codeforces 284 E. Coin Troubles（背包+思维）

题目链接：http://codeforces.com/contest/284/problem/E

题意：n种类型的硬币，硬币的面值可能相同，现在要在满足一些限制条件下求出，用这些硬币构成t面值的方案数；每个限制条件：a,b表示a种类型的硬币要大于b种类型的硬币；

题解：显然如果哪些条件构成环的话就不存在直接输出0。那么可行的情况下要先预处理一下，假设a>b>c>d

那么最少的选择方式是（3，2，1，0）这个必须先预处理一下，然后还有，假如增加a的数量，那么b,c,d的数

量就不受影响，但是如果增加b的数量，那么a的数量肯定要增加，所以还要预处理一个num[i]表示改变i种硬币

需要增加多少。然后就是完全背包了。

#include <iostream>

#include <cstring>

#include <vector>

#include <queue>

#define mod 1000000007

using namespace std;

typedef long long ll;

const int M = 1e5 + 10;

ll a[400] , num[400] , dp[M];

int to[400] , pre[400];

vector<int>vc[400];

void dfs(int pos , int cnt) {

    vc[cnt].push_back(pos);

    if(to[pos] == -1)

        return ;

    dfs(to[pos] , cnt);

}

int main() {

    int n , q , t , u , v;

    scanf("%d%d%d" , &n , &q , &t);

    for(int i = 1 ; i <= n ; i++) {

        scanf("%I64d" , &a[i]);

        to[i] = -1;

        pre[i] = -1;

    }

    while(q--) {

        scanf("%d%d" , &u , &v);

        to[u] = v;

        pre[v] = u;

    }

    int count = 0;

    for(int i = 1 ; i <= n ; i++) {

        if(pre[i] == -1) {

            dfs(i , count);

            count++;

        }

    }

    ll sta = 0;

    int tot = 0;

    for(int i = 0 ; i < count ; i++) {

        int len = vc[i].size();

        tot += len;

        long long sum = 0;

        for(int j = 0 ; j < len ; j++) {

            int pos = vc[i][j];

            sum += a[pos];

            num[pos] = sum;

        }

        sum = 0;

        if(len > 1) {

            for(int j = 0 ; j < len - 1 ; j++) {

                int pos = vc[i][j];

                sum += a[pos];

                sta += sum;

            }

        }

    }

    memset(dp , 0 , sizeof(dp));

    if(sta <= t && tot == n) {

        dp[sta] = 1;

        for(int i = 0 ; i < count ; i++) {

            int len = vc[i].size();

            for(int j = 0 ; j < len ; j++) {

                int pos = vc[i][j];

                for(int k = (int)max(sta , num[pos]) ; k <= t ; k++) {

                    dp[k] += dp[k - num[pos]];

                    dp[k] %= mod;

                }

            }

        }

    }

    printf("%I64d\n" , dp[t] % mod);

    return 0;

}

巴特西

codeforces 284 E. Coin Troubles（背包+思维）

最新文章

热门文章