TIOJ 1411 Ragnarök

poao899    7816K    452MS    G++     0.71K     2009-10-23 12:44:52                                  .

算是DP....吧

想了頗久其實

好像從一兩個月前就在注意這題了


n=10^6所以不O(n)不容易過(?


想了好多奇怪性質

例如說本來以為每個左界的右界有單調性

但是被＋＋－－＋＋＋－打敗了

不過很多人都寫出記憶體超小的超詭異QQ


//*********************************

#include<stdio.h>
#define MAX 1000000
int DP[MAX*2+1],n,sum,max;
int getint(){
    int g=0,c=getchar();
    while(c==10||c==9||c==32)c=getchar();
    if(c==EOF)return -1;
    while(c>='0'&&c<='9'){
        g=g*10+c-48;
        c=getchar();
    }
    return g;
}
int get(){
    char c=getchar();int a=1;
    while(c==10||c==32||c==9)c=getchar();
    if(c=='-')a=-1;
    if(c=='0')a=0;
    while(c!=10)c=getchar();
    return a;
}
main(){
    int *dp=DP;
    while(~(n=getint())){
        for(int i=-n;i<=n;i++)
            dp[i+MAX]=-1;
        sum=max=0;
        dp[MAX]=0;
        for(int i=0;i<n;i++){
            sum+=get();
            //printf("%d %d max%d dp[sum+MAX]%d\n",sum,i,max,dp[sum+MAX]);
            dp[sum+MAX]==-1?dp[sum+MAX]=i+1:max>?=i-dp[sum+MAX]+1;
        }
        printf("%d\n",max);
    }
}