The Fourth Dimension Space

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

POJ 2184 Cow Exhibition 一维DP,需要转化和平移

      这题其实和普通的DP题没什么区别,只是需要用dp[i]表示i状态下能够达到的最大值,而且由于有负数,需要将坐标轴整体平移一下。
在一进一步说,还是要求出所有的状态,类似穷举了。我想了下,如果真的要优化,可以只将出现过的状态记下来,这样扫描的时候可以剪去一些时间,也许0MS就是这么做的吧^_^ ,复杂度O(10^7)。
代码如下:
#include<iostream>
#include
<algorithm>
using namespace std;
#define INF 999999999
int dp[400001];
int n;
int l,r;
#define OFFSET 200000

int main()
{
    fill(dp,dp
+400001,-INF);
    dp[OFFSET]
=0;
    l
=r=OFFSET;
    scanf(
"%d",&n);
    
int i,j;
    
int a,b;
    
for(i=1;i<=n;i++)
    
{
        scanf(
"%d%d",&a,&b);
        
if(a<=0&&b<=0)
            
continue;
        
if(a<0)
        
{

            
int k;
            
for(k=l;k<=r;k++)
            
{

                
if(dp[k]!=-INF)
                
{
                    
if(k+a<l)
                        l
=k+a;

                    
if(dp[k+a]==-INF)
                        dp[k
+a]=dp[k]+b;
                    
else
                        dp[k
+a]=max(dp[k+a],dp[k]+b);
                }

            }

        }


        
else
        
{
            
int k;
            
for(k=r;k>=l;k--)
            
{

                
if(dp[k]!=-INF)
                
{
                    
if(k+a>r)
                        r
=k+a;

                    
if(dp[k+a]==-INF)
                        dp[k
+a]=dp[k]+b;
                    
else
                        dp[k
+a]=max(dp[k+a],dp[k]+b);
                }

            }


        }

    




    }

    
int res=0;
    
int k;
    
for(k=OFFSET;k<=OFFSET+1000*n;k++)
    
{

        
if(dp[k]>0&&k-OFFSET+dp[k]>res)
            res
=k-OFFSET+dp[k];
    }

    printf(
"%d\n",res);
    
return 0;
}

posted on 2010-03-13 00:24 abilitytao 阅读(1475) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理