Codeforces 284E Coin Troubles 思维+完全背包计数

E. Coin Troubles
time limit per test 2 seconds
memory limit per test 256 megabytes
input standard input
output standard output
In the Isle of Guernsey there are n different types of coins. For each i (1 ≤ i ≤ n), coin of type i is worth ai cents. It is possible that ai = ajfor some i and j (i ≠ j).

Bessie has some set of these coins totaling t cents. She tells Jessie q pairs of integers. For each i (1 ≤ i ≤ q), the pair bi, ci tells Jessie that Bessie has a strictly greater number of coins of type bi than coins of type ci. It is known that all bi are distinct and all ci are distinct.

Help Jessie find the number of possible combinations of coins Bessie could have. Two combinations are considered different if there is some i (1 ≤ i ≤ n), such that the number of coins Bessie has of type i is different in the two combinations. Since the answer can be very large, output it modulo 1000000007 (109 + 7).

If there are no possible combinations of coins totaling t cents that satisfy Bessie's conditions, output 0.

Input
The first line contains three space-separated integers, n, q and t (1 ≤ n ≤ 300; 0 ≤ q ≤ n; 1 ≤ t ≤ 105). The second line contains n space separated integers, a1, a2, ..., an (1 ≤ ai ≤ 105). The next q lines each contain two distinct space-separated integers, bi and ci(1 ≤ bi, ci ≤ n; bi ≠ ci).

It's guaranteed that all bi are distinct and all ci are distinct.

Output
A single integer, the number of valid coin combinations that Bessie could have, modulo 1000000007 (109 + 7).

Examples
input
4 2 17
3 1 2 5
4 2
3 4
output
3
input
3 2 6
3 1 1
1 2
2 3
output
0
input
3 2 10
1 2 3
1 2
2 1
output
0
Note
For the first sample, the following 3 combinations give a total of 17 cents and satisfy the given conditions: {0 of type 1, 1 of type 2, 3 of type 3, 2 of type 4}, {0, 0, 6, 1}, {2, 0, 3, 1}.

No other combinations exist. Note that even though 4 occurs in both bi and ci,  the problem conditions are still satisfied because all bi are distinct and all ci are distinct.

OJ

​​CodeForces - 284E ​​ Coin Troubles

题意

有n种硬币，现在我们需要凑出t价值的硬币，我们每种硬币都可以任取数量，不过要满足q个约束。

对于每个约束，（a，b）表示需要a种类的硬币使用的个数>b种类的硬币。

思路

如果num[u]>num[v],我们可以得出：

• u至少选一个，因为如果u和v都不选，0,0也是不满足题意的,这一步我们可以把总价值t减少a[u]
• val[v]+=val[u],因为t已经选择了一个u，所以对于v来说再选跟v一样数量的即可

最后注意谈判一下环即可。

 

#include <bits/stdc++.h>
using namespace std;
const int N=505;
const int M=100005;
typedef long long LL;
const int mod = 1e9 + 7;
int dp[M],in[N],G[N],a[N];
int n,q,t,u,v;
int cal()
{
    while(q--)
    {
        int u=0;
        for(int i=1;i<=n;i++)
        {
           if(in[i]==0&&G[i]!=0)
           {
               u=i;
               break;
           }
        }

        if(u==0)
            return 0;
        t-=a[u];
        if(t<0)
            return 0;

        int v=G[u];
        G[u]=0;
        in[v]--;
        a[v]+=a[u];

    }

    dp[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=a[i];j<=t;j++)
        {
            dp[j]=(dp[j]+dp[j-a[i]])%mod;
        }

    return dp[t];
}
int main()
{

    scanf("%d %d %d",&n,&q,&t);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d",&a[i]);
    }


    for(int i = 1; i <= q; i++)
    {
        scanf("%d %d",&u,&v);
        in[v]++;
        G[u]=v;
    }




    printf("%d\n",cal());
    return 0;
}