如果一開始我也用兩個(gè)dp數(shù)組就好了，但是我錯(cuò)誤地認(rèn)為如果從后往前掃描數(shù)組的話是不會(huì)出現(xiàn)相互影響的情況的，事實(shí)上我錯(cuò)了，原來數(shù)據(jù)里有重量為0的數(shù)據(jù)，如果有一對(duì)寶藏他們有兩種取法（如第二種情況）而這兩件寶物的重量又恰好為0，那么用 dp[j]=dp[j-w]+v[i] 這個(gè)狀態(tài)轉(zhuǎn)移方程相當(dāng)于兩件寶物都取了，這違背了題意，除了這一種情況之外，其他的情況都可以直接用上面的轉(zhuǎn)移方程式（所以說這個(gè)題真的很猥瑣，但也體現(xiàn)出我對(duì)背包問題掌握的不全面）。
當(dāng)我知道了這個(gè)陷阱后，我極力的想證明只有都是0的情況才不能用上面的方法，所以我只開了一個(gè)dp數(shù)組，事實(shí)上證明我是正確的！這個(gè)題糾結(jié)了較長(zhǎng)時(shí)間，雖然能比當(dāng)場(chǎng)做出來的同學(xué)想的更清晰，但是總是現(xiàn)場(chǎng)卡題也不是個(gè)好現(xiàn)象，有則改之吧。
#include<iostream>
using namespace std;
#define max(a,b) (a>b?a:b)
#define MAX 10001
struct node
{
int w1,v1,w2,v2,flag;
}l[MAX];
int dp[50001];
int main()
{
int bagw;
int n;
int i,j;
while(scanf("%d%d",&bagw,&n)!=EOF)
{
bagw/=100;
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
{
scanf("%d%d%d%d%d",&l[i].w1,&l[i].v1,&l[i].w2,&l[i].v2,&l[i].flag);
l[i].w1/=100;
l[i].w2/=100;
}
for(i=1;i<=n;i++)
{
for(j=bagw;j>=0;j--)
{
int temp=dp[j];
if(l[i].flag==1)
{
int pos=j-l[i].w1-l[i].w2;
if(pos>=0)
dp[j]=max(dp[j],dp[pos]+l[i].v1+l[i].v2);
}
if(l[i].flag==2)
{
int pos=j-l[i].w1;
if(pos>=0)
{
if(max(dp[j],dp[pos]+l[i].v1)>temp)
{
temp=max(dp[j],dp[pos]+l[i].v1);
}
}
pos=j-l[i].w2;
if(pos>=0)
{
if(max(dp[j],dp[pos]+l[i].v2)>temp)
temp=max(dp[j],dp[pos]+l[i].v2);
}
dp[j]=temp;
}
if(l[i].flag==3)
{
int pos=j-l[i].w1;
if(pos>=0)
{
if(max(dp[j],dp[pos]+l[i].v1)>temp)
{
temp=max(dp[j],dp[pos]+l[i].v1);
}
}
pos=j-l[i].w1-l[i].w2;
if(pos>=0)
{
if(max(dp[j],dp[pos]+l[i].v1+l[i].v2)>temp)
{
temp=max(dp[j],dp[pos]+l[i].v1+l[i].v2);
}
}
dp[j]=temp;
}
}
}
int res=0;
for(i=1;i<=bagw;i++)
{
if(res<dp[i])
res=dp[i];
}
printf("%d\n",res);
}
return 0;
}
topcoder SRM 又快到了，希望自己能正常發(fā)揮，不過這次是DIV 1了，希望題目不要太難 ，呵呵 加油啦 ^_^