PKU-3356: AGTC

解法

編集距離を求めるだけ。テストケースが実は複数ある。stdio.hをincludeしなくてもEOFは-1らしい。

int dp[1002][1002];
char s1[1002], s2[1002];
int N, M;

int solve(){
    int i,j,c;
    for(i=0;i<=N;i++)dp[i][0]=i;
    for(j=0;j<=M;j++)dp[0][j]=j;
    for(i=1;i<=N;i++)for(j=1;j<=M;j++){
        c = s1[i-1]==s2[j-1]?0:1;
        dp[i][j] = dp[i-1][j]+1;
        if(dp[i][j] > dp[i][j-1]+1) dp[i][j] = dp[i][j-1]+1;
        if(dp[i][j] > dp[i-1][j-1]+c) dp[i][j] = dp[i-1][j-1]+c;
    }
    return dp[N][M];
}

main(){
    while(scanf("%d %s %d %s ",&N,s1,&M,s2)+1)
        printf("%d\n",solve());
}