首页 > 代码库 > C. Coin Troubles 有依赖的背包 + 完全背包变形
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 = 300 + 20; int fa[maxn], a[maxn]; bool out[maxn]; int n, q, val; struct node { int u, v, tonext; }e[maxn * 2]; 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 << 0 << endl; exit(0); } vis[v] = true; dfs(v); vis[v] = false; } } void calc(int cur, int ti) { if (cur == 0) return; val -= a[cur] * ti; if (val < 0) { //不能等于 cout << 0 << endl; exit(0); } calc(fa[cur], ti + 1); a[cur] += a[fa[cur]]; } int dp[100000 + 20]; const int MOD = 1e9 + 7; void work() { cin >> n >> q >> val; for (int i = 1; i <= n; ++i) { cin >> a[i]; } for (int i = 1; i <= q; ++i) { int u, v; cin >> u >> v; fa[v] = u; out[u] = true; add(u, v); } for (int i = 1; i <= n; ++i) { // if (vis[i]) continue; vis[i] = true; dfs(i); vis[i] = false; } for (int i = 1; i <= n; ++i) { if (out[i]) continue; calc(i, 0); } dp[0] = 1; for (int i = 1; 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 0; }
C. Coin Troubles 有依赖的背包 + 完全背包变形
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。