CSU 1529 Equator DP - c++编程基础

队列优化DP

Equator

Time Limit: 5000MS

Memory Limit: 131072KB

64bit IO Format: %lld & %llu

Submit Status

Description

Input

Output

Sample Input

3 3 1 2 3 8 4 5 -1 -1 1 -1 -1 5 2 -1 -1

Sample Output

6 14 0

/* ***********************************************
Author        :CKboss
Created Time  :2015年03月17日 星期二 20时13分17秒
File Name     :CSU1529.cpp
************************************************ */

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include
             using namespace std; const int maxn=2000200; int n,ans; int a[maxn]; int sum[maxn]; int dq[maxn],head,tail; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int T_T; scanf("%d",&T_T); while(T_T--) { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",a+i); a[n+i]=a[i]; } for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i]; head=0;tail=-1;ans=0; for(int i=1;i<=2*n;i++) { while((head<=tail)&&(sum[i]-sum[dq[tail]]<0)) { ans=max(ans,sum[dq[tail]]-sum[dq[head]]); tail--; } while((head<=tail)&&(i-dq[head]>n)) { ans=max(ans,sum[dq[tail]]-sum[dq[head]]); head++; } dq[++tail]=i; } printf("%d\n",ans); } return 0; }