NYOJ 49 开心的小明

举报
Linux猿 发表于 2021/08/04 23:59:46 2021/08/04
【摘要】 题目链接~~> 做题感悟:这题就是一个背包的变形,具体见代码。 代码: #include<stdio.h>#include<iostream>#include<map>#include<string>#include<string.h>#include<stdlib.h>#include&lt...

题目链接~~>

做题感悟:这题就是一个背包的变形,具体见代码。

代码:


      #include<stdio.h>
      #include<iostream>
      #include<map>
      #include<string>
      #include<string.h>
      #include<stdlib.h>
      #include<math.h>
      #include<vector>
      #include<queue>
      #include<algorithm>
      using namespace std ;
      const int INF = -999999 ;
      const int MX= 50005 ;
      int dp[MX] ;
      int main()
      {
      int T,c,n ;
      scanf("%d",&T) ;
      while(T--)
       {
      scanf("%d%d",&c,&n) ;
      int v,w ;
      memset(dp,0,sizeof(dp)) ;
      for(int i=0 ;i<n ;i++)
       {
      scanf("%d%d",&v,&w) ;
      for(int j=c ;j>=v ;j--) // 逆序
      if(dp[j]<dp[j-v]+v*w)
       dp[j]=dp[j-v]+v*w ;
       }
      printf("%d\n",dp[c]) ;
       }
      return 0 ;
      }
  
 


 

文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/nyist_zxp/article/details/20644403

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。