CSU 1529 Equator DP

2015-07-20 17:10:01 来源: 作者: 浏览: 2

?

队列优化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; }
           
          
         
        
       
      
     
    
   
  


?

?

?

-->

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: