首页 > 代码库 > CodeForces 283C Coin Troubles 分析+背包思想
CodeForces 283C Coin Troubles 分析+背包思想
很灵活的题目,题意简单,看到又是钱币问题,类似于那种给了一定数目T,有n种钱币,每种的价值,让你组合成总价值为T的方案数,但是加了一些限制条件,那就是某些种类钱币数量必须大于另一些种类的,加了个限制条件 我就脑残了,唉智商看来是真不够啊 ,后来看了别人的分析
倘若种类a的钱币数量必须要大于种类b的数量,那么如果我要 去 m张b种类的钱币,其实同时也是相当于已经取了m张a种类的,因为a必须大于b的嘛,所以我们可以通过这样来修改题目给的钱币的价值,若a种类数量必须大于b种类数量,且a种类价值为A,b种类为B,那么可以把 b种类的钱币修改为 A + B,同时要凑成的总价值T要先减去 !!!一个!!!a种类钱币的价值,这样后面随便怎么取都能满足 所取的方案 a种类数量大于b种类数量
这样就可以进行仿造背包的思想来进行递推求解了
恍然大悟去敲了
但是WA了很久,后来真是是已经WA了无数把了,没办法 看了别人的代码,发现 前面多了一些处理的东西,原来题目给的限制条件 比如有 a种类必须大于b种类,同时b要大于c,但是又有可能会出现c会大于a的, 这样就有环了,题目 所说的 给了q组限制条件,每组包含bi,ci 它说bi中不会重复出现相同的数,ci中也不会,但是bi 与cj还是有可能相同的,所以会有 环的情况出现,还是读题不够仔细啊 ,题目不错的,分析过程揭开以后觉得不难,但是下手 感觉没法出手,是个好题目
http://codeforces.com/contest/283/problem/C
#include<iostream> #include<cstdio> #include<list> #include<algorithm> #include<cstring> #include<string> #include<queue> #include<stack> #include<map> #include<vector> #include<cmath> #include<memory.h> #include<set> #define ll long long #define eps 1e-8 const int inf = 0xfffffff; const ll INF = 1ll<<61; using namespace std; //vector<pair<int,int> > G; //typedef pair<int,int > P; //vector<pair<int,int> > ::iterator iter; // //map<ll,int >mp; //map<ll,int >::iterator p; #define MOD 1000000007 int nn[355]; int b[355]; int c[355]; int father[355]; int in[355]; ll dp[1000000 + 5]; bool flag; void init() { memset(nn,0,sizeof(nn)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); memset(in,0,sizeof(in)); memset(father,0,sizeof(father)); memset(dp,0ll,sizeof(dp)); flag = false; } void input(int &n,int &q,int &t) { scanf("%d %d %d",&n,&q,&t); for(int i=1;i<=n;i++) scanf("%d",&nn[i]); for(int i=0;i<q;i++) { scanf("%d %d",&b[i],&c[i]); father[b[i]] = c[i]; in[c[i]]++; } } void cal(int &n,int &q,int &t) { for(int i=0;i<q;i++) { int tmp = 0; for(int j=1;j<=n;j++) { if(father[j] && in[j] == 0) { tmp = j;break; } } if(!tmp) {puts("0");flag = true;return ;} int pre = father[tmp]; in[pre]--; father[tmp] = 0; t -= nn[tmp]; nn[pre] += nn[tmp]; if(t < 0) {puts("0");flag = true;return ;} } } void DP(int &n,int &t) { dp[0] = 1;//都不取 for(int i=1;i<=n;i++) { if(nn[i] > t)continue; for(int j=0;j + nn[i] <= t;j++) dp[j + nn[i]] = (dp[j + nn[i]] + dp[j])%MOD; } } void output(int &t) { printf("%I64d\n",dp[t]); } int main() { int n,q,t; init(); input(n,q,t); cal(n,q,t); if(flag)return 0; DP(n,t); output(t); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。