[poj 2479] Maximum sum -- 转载

转自 CSND

想看更多的解题报告: http://blog.csdn.net/wangjian8006/article/details/7870410
转载请注明出处：http://blog.csdn.net/wangjian8006

题目大意：对于连续的整数和的串s1和s2，s1与s2不相交，使得s1+s2最大
解题方法： DP。
lt[i]代表以第i个元素结尾的串最大值
rt[i]代表以第i个元素开头的串的最大值
那么设置一个rtm[i]代表取后i个元素之中最大连续子串的和

很显然，lt[i]=max(a[i],lt[i-1]+a[i]);
rt[i]=max(a[i],rt[i+1]+a[i]);
rtm[i]=max(rtm[i+1],rt[i]);

此题与poj2593一模一样，但是要将MAXV改成10010就可以A了

 #include <iostream>

 using namespace std;

 #define max(a,b) a>b?a:b

 #define MAXV 50010

 #define inf -10010

 int lt[MAXV],rt[MAXV],a[MAXV],rtm[MAXV];

 int main(){

     int t,n,i,temp;

     scanf("%d",&t);

     while(t--){

         scanf("%d",&n);

         for(i=;i<=n;i++)

             scanf("%d",&a[i]);

         temp=inf;lt[]=a[];rt[n]=a[n];

         for(i=;i<=n;i++){

             lt[i]=max(a[i],lt[i-]+a[i]);

         }

         for(i=n-;i>=;i--){

             rt[i]=max(a[i],rt[i+]+a[i]);

         }

         rtm[n]=rt[n];

         for(i=n-;i>=;i--)

             rtm[i]=max(rtm[i+],rt[i]);

         int ma=inf;

         for(i=;i<=n;i++){

             ma=max(ma,lt[i-]+rtm[i]);

         }

         printf("%d\n",ma);

     }

     return ;

 }

巴特西

[poj 2479] Maximum sum -- 转载

最新文章

热门文章