2213: [Poi2011]Difference

stupid_lulu posted @ 2013年3月20日 21:42 in poi , 1129 阅读

裸扫一遍。。记下状态。注意一段中没有一个字母就不能算他为出现最少的字母= =!

#include<cstdio>
int n,ans=0;
char st[1000002];
int f[41][41],g[41][41];
int max(int a,int b){return a>b? a:b;}
int main(){
    scanf("%d",&n);
    scanf("%s",st);
    for (int i=0;i<n;i++){
        int y=st[i]-'a';
        for (int j=0;j<26;j++){
            f[j][y]++;
            f[y][j]--;
            if (!g[y][j]) g[y][j]=1;
            if (g[y][j]==2){g[y][j]=1;f[y][j]++;}
            if (f[y][j]<=-1){f[y][j]=-1;g[y][j]=2;}
            if (g[y][j]) ans=max(ans,f[y][j]);
            if (g[j][y]) ans=max(ans,f[j][y]);
            //printf("f[%c][%c]=%d f[%c][%c]=%d ",j+'a',y+'a',f[j][y],y+'a',j+'a',f[y][j]);
        }
        //printf("\n");
    }
    printf("%d\n",ans);
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter