记录编号	581588	评测结果	AAAAAAAAAA
题目名称	串串	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-08-06 14:33:28	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
char a[110],b[110];
int dp[110][110];
int main(){
    freopen("painter.in","r",stdin);
    freopen("painter.out","w",stdout);
    while(cin>>a+1>>b+1){
        int l = strlen(a+1);
        for(int i = 1;i <= l;i++)dp[i][i] = 1;
        for(int len = 2;len <= l;len++){
            for(int i = 1;i+len-1 <= l;i++){
                int j = i+len-1;
                dp[i][j] = 0x3f3f3f3f;
                if(b[i] == b[j])dp[i][j] = min(dp[i+1][j],dp[i][j-1]);
                else{
                    for(int k = i;k < j;k++){
                        dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]);
                    }
                }
            }
        }
        for(int i = 1;i <= l;i++){
            if(a[i] == b[i])dp[1][i] = dp[1][i-1];
            else{
                for(int j = 1;j < i;j++){
                    dp[1][i] = min(dp[1][i],dp[1][j]+dp[j+1][i]);
                }
            }
        }
        printf("%d\n",dp[1][l]);
    }
    
    return 0; 

}