记录编号	581920	评测结果	AAAAAAAAAA
题目名称	串串	最终得分	100
用户昵称	宇战	是否通过	通过
代码语言	C++	运行时间	0.032 s
提交时间	2023-08-29 19:22:08	内存使用	1.15 MiB

    #include<bits/stdc++.h>
    using namespace std;
    char s1[110],s2[110];
    string a,b;
    int n,m,s;
    int main(){
        freopen("painter.in","r",stdin);
        freopen("painter.out","w",stdout);
        while(cin>>a>>b){
            int l=a.size();
            int dp[110][110];
            for(int i=0;i<=l-1;i++){
                s1[i+1]=a[i];
                s2[i+1]=b[i];
            }
            for(int i=1;i<=l;i++){
                dp[i][i]=1;
            }
            for(int len=2;len<=l;len++){
                for(int i=1;i<=l-len+1;i++){
                    int j=i+len-1;
                    dp[i][j]=0x3f3f3f3f;
                    if(s2[i]==s2[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(s1[i]==s2[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]);
                }}
            }        
            cout<<dp[1][l]<<endl;
     
        }
        
        return 0;
    }