C. Coin Troubles 有依赖的背包 + 完全背包变形

http://codeforces.com/problemset/problem/283/C

一开始的时候，看着样例不懂，为什么5 * a1 + a3不行呢?也是17啊

原来是，题目要求硬币数目a3 > a4 > a2，那么，不选的话，是不合法的。就是0、0、0这样是不合法的，因为a3 = a4了。

那么就可以知道， a3起码都要选两个了。

那么怎么维护这个关系呢？，思路是有依赖的背包，需要a3的数目比a4的多，就可以把a4那件物品变成a3 + a4

那么每一次选择的时候，就隐含地选了一件a3了。当然，前提是起码已经选了2件a3、1件a4、0件a2

然后把需要求的val减去一定要选的东西后，做一个完全背包就好了。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int maxn =  + ;

int fa[maxn], a[maxn];

bool out[maxn];

int n, q, val;

struct node {

    int u, v, tonext;

}e[maxn * ];

int first[maxn];

int num;

void add(int u, int v) {

    ++num;

    e[num].u = u;

    e[num].v = v;

    e[num].tonext = first[u];

    first[u] = num;

}

bool vis[maxn];

void dfs(int cur) {

    for (int i = first[cur]; i; i = e[i].tonext) {

        int v = e[i].v;

        if (vis[v]) {

            cout <<  << endl;

            exit();

        }

        vis[v] = true;

        dfs(v);

        vis[v] = false;

    }

}

void calc(int cur, int ti) {

    if (cur == ) return;

    val -= a[cur] * ti;

    if (val < ) { //不能等于

        cout <<  << endl;

        exit();

    }

    calc(fa[cur], ti + );

    a[cur] += a[fa[cur]];

}

int dp[ + ];

const int MOD = 1e9 + ;

void work() {

    cin >> n >> q >> val;

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

        cin >> a[i];

    }

    for (int i = ; i <= q; ++i) {

        int u, v;

        cin >> u >> v;

        fa[v] = u;

        out[u] = true;

        add(u, v);

    }

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

//        if (vis[i]) continue;

        vis[i] = true;

        dfs(i);

        vis[i] = false;

    }

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

        if (out[i]) continue;

        calc(i, );

    }

    dp[] = ;

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

        for (int j = a[i]; j <= val; ++j) {

            dp[j] += dp[j - a[i]];

            if (dp[j] >= MOD) dp[j] %= MOD;

        }

    }

    cout << dp[val] << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    IOS;

    work();

    return ;

}