The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

浙大月赛 3264 DP

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

posted on 2009-11-17 01:39 abilitytao 阅读(1512) 评论(5)  编辑 收藏 引用

评论

# re: 浙大月赛 3264 DP 2009-11-18 09:01 tp

最好把题目一起发出来,,,
  回复  更多评论   

# re: 浙大月赛 3264 DP 2009-11-18 16:30 Best

学习了,顶个。。。。  回复  更多评论   

# re: 浙大月赛 3264 DP 2009-11-18 22:18 littletom

难怪我用
f[j]=max(f[j],f[j-w1]+v1);
f[j]=max(f[j],f[j-w2]+v2);
就WA

int tp = f[j];
tp=max(tp,f[j-w1]+v1);
tp=max(tp,f[j-w2]+v2);
f[j]=tp;
就AC了
强 !!你是怎么知道数据中有0这组的,太强大了!我就没有想到,只是觉得自己发现了问题,可是没有继续追寻啊!!学习。。。。  回复  更多评论   

# re: 浙大月赛 3264 DP 2009-11-19 12:32 swcai

还是两维dp数组比较好,压根就没想到这个事情。做这些题目给我一个印象就是不要管细节的执行效率和内存使用效率,能跑,AC就行那  回复  更多评论   

# re: 浙大月赛 3264 DP 2009-11-22 14:29 梦芭莎内衣

圣诞节快放假看电视  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理