如果一開始我也用兩個dp數組就好了，但是我錯誤地認為如果從后往前掃描數組的話是不會出現相互影響的情況的，事實上我錯了，原來數據里有重量為0的數據，如果有一對寶藏他們有兩種取法（如第二種情況）而這兩件寶物的重量又恰好為0，那么用 dp[j]=dp[j-w]+v[i] 這個狀態轉移方程相當于兩件寶物都取了，這違背了題意，除了這一種情況之外，其他的情況都可以直接用上面的轉移方程式（所以說這個題真的很猥瑣，但也體現出我對背包問題掌握的不全面）。
當我知道了這個陷阱后，我極力的想證明只有都是0的情況才不能用上面的方法，所以我只開了一個dp數組，事實上證明我是正確的！這個題糾結了較長時間，雖然能比當場做出來的同學想的更清晰，但是總是現場卡題也不是個好現象，有則改之吧。
#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 又快到了，希望自己能正常發揮，不過這次是DIV 1了，希望題目不要太難 ，呵呵 加油啦 ^_^