博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
!HDU 2602 Bone Collector--DP--(裸01背包)
阅读量:4970 次
发布时间:2019-06-12

本文共 832 字,大约阅读时间需要 2 分钟。

题意:这题就是一个纯粹的裸01背包

分析:WA了好几次。01背包实现的一些细节没搞懂

1.为什么dp[i][j]赋初值为0而不是value[i]。由于第i个石头可能不放!

2.在进行状态转移之前要dp[i][j]=dp[i-1][j],不然肯定会WA啊。想想就明确了

3.终于结果是dp[n][v],不是每次求mx,由于状态转移就是这么推的啊

代码:

#include
#include
#include
using namespace std;long long dp[1001][1001],va[1001],mx;int t,n,v,vo[1001];int main(){ cin>>t; while(t--){ cin>>n>>v; mx=-1; for(int i=1;i<=n;i++) cin>>va[i]; for(int i=1;i<=n;i++) cin>>vo[i]; for(int i=1;i<=n;i++) for(int j=0;j<=v;j++) dp[i][j]=0; //错误1 for(int i=1;i<=n;i++){ for(int j=0;j<=v;j++){ dp[i][j]=dp[i-1][j]; //错误2 if(vo[i]<=j) dp[i][j]=dp[i][j]>dp[i-1][j-vo[i]]+va[i]?dp[i][j]:dp[i-1][j-vo[i]]+va[i]; } } mx=dp[n][v]; //错误3 cout<
<

转载于:https://www.cnblogs.com/llguanli/p/8416366.html

你可能感兴趣的文章
Strict Standards: Only variables should be passed by reference
查看>>
hiho_offer收割18_题解报告_差第四题
查看>>
AngularJs表单验证
查看>>
静态方法是否属于线程安全
查看>>
02号团队-团队任务3:每日立会(2018-12-05)
查看>>
SQLite移植手记1
查看>>
js05-DOM对象二
查看>>
mariadb BINLOG_FORMAT = STATEMENT 异常
查看>>
C3P0 WARN: Establishing SSL connection without server's identity verification is not recommended
查看>>
iPhone在日本最牛,在中国输得最慘
查看>>
动态方法决议 和 消息转发
查看>>
js 基础拓展
查看>>
C#生成随机数
查看>>
Android应用程序与SurfaceFlinger服务的连接过程分析
查看>>
Java回顾之多线程
查看>>
机电行业如何进行信息化建设
查看>>
9、总线
查看>>
Git 笔记 - section 1
查看>>
2018 Multi-University Training Contest 10 - Count
查看>>
HDU6203 ping ping ping
查看>>