TIOJ 1444 郵局設置問題 [Tree] = UVa 10459

poao899    1444    Accepted    280K    181MS    G++    1.43K    2010-03-31 15:04:42                         .




同UVa 10459The  Tree Root

不過那題輸出好機車= =

Best Roots  : 1
Worst Roots : 4 5 6 7

第一行是兩個空白啦囧囧囧



Tree DP　O(n)    結束























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

#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();
            dp[sum+MAX]==-1?dp[sum+MAX]=i+1:max>?=i-dp[sum+MAX]+1;
        }
        printf("%d\n",max);
    }
}