如果一开始我也用两个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了，希望题目不要太难 ，呵呵 加油啦 ^_^