1481:Maximum sum （前缀和+dp）

【题目描述】

　　　　对一个序列A={a1, a2,..., an}给出函数：

                     t1     t2 
         d(A) = max{ ∑ai + ∑aj | 1 <= s1 <= t1 < s2 <= t2 <= n }
                    i=s1   j=s2
求出该函数最大值。

【题目链接】

　　　　http://noi.openjudge.cn/ch0206/1481/

【算法】

　　　　类似股票买卖，决策一个i的位置，i之前的最大子段和和i+1及其之后的最大子段和的最大值。注意前i个最大子段和的求法：要记录一个前缀和最小值，注意初始化应当为a【1】和0的较小值（wa了半天才发现）。

【代码】

 #include <bits/stdc++.h>

 using namespace std;

 int t,n,i;

 int a[],pre[],post[];

 int main()

 {

     scanf("%d",&t);

     while(t--) {

         memset(pre,,sizeof(pre));

         memset(post,,sizeof(post));

         scanf("%d",&n);

         for(i=;i<=n;i++) scanf("%d",&a[i]),a[i]+=a[i-];

         pre[]=a[];

         int minn=min(,a[]);

         for(i=;i<n;i++) minn=min(minn,a[i]),pre[i]=max(pre[i-],a[i]-minn);

         post[n]=a[n]-a[n-];

         int maxn=a[n];

         for(i=n-;i>;i--) maxn=max(maxn,a[i]),post[i]=max(post[i+],maxn-a[i-]);

         int ans=-1e9;

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

             ans=max(ans,pre[i]+post[i+]);

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

     }

     return ;

 }

巴特西

1481:Maximum sum （前缀和+dp）

最新文章

热门文章