1513.cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 29 行

#include<stdio.h>
int min(int a,int b,int c){
    return a>b?b>c?c:b:a>c?c:a;
}
int pre[5001],cur[5001];
int main()
{
    char str[5001];
    int n,i,j,t1,t2,t3;
    while(scanf("%d",&n)==1){
        scanf("%s",str);
        for(i=1;i<n;i++){
            pre[i]=0;
            for(j=i-1;j>=0;j--){
                t1=cur[j+1];
                t2=pre[j];
                t3=pre[j+1];
                if(str[i]!=str[j])
                    t3=9999;
                cur[j]=min(t1+1,t2+1,t3);
            }
            for(j=0;j<i;j++)
                pre[j]=cur[j];
        }
        printf("%d\n",cur[0]);
    }
    return 0;
}