给 n 中 钱币。以及每两种钱币的关系,表示,ai 的 个数 要大于 bi 组合成一个价值val,求方案数,好奇妙的一个处理方式,不得不说又学到了
#include<stdio.h>
#include<vector>
#include<cstring>
#include<iostream>
using namespace std;
const int mod = 1e9 + 7;
const int M = 1e5 + 1;
long long dp[M];
int a[500],in[500],father[500];int main(){int n,m,t,u,v;while(cin >> n >> m >> t){memset(in,0,sizeof(in));memset(father,0,sizeof(father));memset(dp,0,sizeof(dp)); int x = m;// memset(che,0,sizeof(che));for(int i=1;i<=n;i++) cin >> a[i];while(m --){cin >> u >> v;in[v] ++ ;father[u] = v;}for(int i=0;i<x;i++){int pos = 0;for(int j=1;j<=n;j++){if(father[j] && !in[j]){pos = j;break;}}// cout << pos <<endl;if(!pos){puts("0");return 0;}int pre = father[pos];father[pos] = 0;in[pre] --;t -= a[pos];a[pre] += a[pos];if(t < 0){puts("0");return 0;}}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;}}//cout << t <<endl;cout << dp[t] <<endl;}
}