[HDU 2602]Bone Collector ( 0-1背包水题 )

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2602

水题啊水题

还给我WA了好多次

因为我在j<w[i]的时候状态没有下传。。

 #include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define PB push_back
#define SZ size()
#define X first
#define Y second int T,N,V;
int dp[][];
int w[],v[]; int main(){
scanf("%d",&T);
while( T-- ){
scanf("%d%d",&N,&V);
for(int i=;i<=N;i++){
scanf("%d",&v[i]);
}
for(int i=;i<=N;i++){
scanf("%d",&w[i]);
}
memset(dp,,sizeof(dp));
for(int i=;i<=N;i++){
for(int j=;j<=V;j++) if(j>=w[i]){
dp[i][j] = max(dp[i-][j-w[i]]+v[i],dp[i-][j]);
} else {
dp[i][j] = dp[i-][j];
}
}
printf("%d\n",dp[N][V]);
}
return ;
}
上一篇:【LeetCode】87. Scramble String


下一篇:[原]hdu2602 Bone Collector (01背包)