nyist 311 完全背包

网友投稿 746 2022-10-08

nyist 311 完全背包

nyist 311 完全背包

题目地址：#include #include #include #include #include #include #include #include #include #include const int inf = 0x3f3f3f3f;//1061109567typedef long long LL;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int dp[50010];int main(){ int t; scanf("%d",&t); while(t--) { int m,v; memset(dp,-1,sizeof(dp)); dp[0] = 0; scanf("%d%d",&m,&v); for(int i=1; i<=m; i++) { int c,w; scanf("%d%d",&c,&w); for(int j=c; j<=v; j++) { if(dp[j-c] != -1) { dp[j] = max(dp[j],dp[j-c] + w); } } } if(dp[v] != -1) printf("%d\n",dp[v]); else printf("NO\n"); } return 0;}

AC代码2：（初始化为一个很大的负数，上一种方法比较好）

#include #include #include #include #include #include #include #include #include #include #include const int inf = 0x3f3f3f3f;//1061109567typedef long long LL;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int dp[50010];int main(){ int t; scanf("%d",&t); while(t--) { int m,v; memset(dp,-inf,sizeof(dp)); dp[0] = 0; scanf("%d%d",&m,&v); for(int i=1; i<=m; i++) { int c,w; scanf("%d%d",&c,&w); for(int j=c; j<=v; j++) { dp[j] = max(dp[j],dp[j-c] + w); } } if(dp[v] > 0) printf("%d\n",dp[v]); else printf("NO\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：代码
上一篇:基于flask框架的12306抢票程序
下一篇:HoloJS- 创建 UWP 应用程序的框架
相关文章

 发表评论

暂时没有评论，来抢沙发吧~