设为首页 加入收藏

TOP

CodeForces 283C Coin Troubles 分析+背包思想
2015-07-20 18:02:26 来源: 作者: 【大 中 小】 浏览:2次
Tags：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还是有可能相同的，所以会有 环的情况出现，还是读题不够仔细啊 ，题目不错的，分析过程揭开以后觉得不难，但是下手 感觉没法出手，是个好题目

?

?

?

?

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 const int inf = 0xfffffff; const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::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
                    
                      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 ,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; }


?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：HDU 2126 Buy the souvenirs 下一篇：HDU 2830 Matrix Swapping II （..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: