FZU - 2024 LCS && EditStep

タイトル:
a,bの2文字列,長さLen(1<=Len<=1000)を与え,これら2文字列のLCS長とEditStepをそれぞれ求める.次のようになります.
LCSは、2つの文字列の最長共通サブストリングです.
EditStepは、1文字を追加したり、1文字を削除したり、1文字を置き換えたりして、a列とb列を同じにするために必要な操作個数です.
考え方:LCSは言わないが、EditStepは:ans[i][j]がstr 1の前i、str 2の前jの最小ステップ数を表し、3つの場合、削除、追加、置換、削除と置換の効果は同じであり、str 1[i]=str 2[j]であればdp[i-1][j-1]となり、等しくなければ、置換すればこれに加えて+1となり、すべての場合の最小値をとる

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1005;

char str1[MAXN],str2[MAXN];
int dp[MAXN][MAXN];
int ans[MAXN][MAXN];

int main(){
    int t,cas=1;
    scanf("%d%*c",&t);
    while (t--){
        scanf("%s%s",str1,str2);
        memset(dp,0,sizeof(dp));
        int len1 = strlen(str1),len2 = strlen(str2);
        for (int i = 0; i <= len1; i++)
            ans[i][0] = i;
        for (int j = 0; j <= len2; j++)
            ans[0][j] = j;
        int t;
        for (int i = 1; i <= len1; i++)
            for (int j = 1; j <= len2; j++){
                if (str1[i-1] == str2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    t = 0;
                }
                else {
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                    t = 1;
                }
                ans[i][j] = min(ans[i-1][j-1]+t,min(ans[i-1][j]+1,ans[i][j-1]+1));
            }
        printf("Case %d: LCS=%d EditStep=%d
",cas++,dp[len1][len2],ans[len1][len2]);
    }
    return 0;
}