P1435 回文字串

倚窗倾听风吹雨

https://www.luogu.org/problemnew/show/P1435

题目背景
IOI2000第一题

题目描述
回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。

比如 “Ab3bd”插入2个字符后可以变成回文词“dAb3bAd”或“Adb3bdA”，但是插入少于2个的字符无法变成回文词。

注：此问题区分大小写

输入输出格式
输入格式：
一个字符串(0<strlen<=1000)

输出格式：
有且只有一个整数，即最少插入字符数

输入输出样例
输入样例#1：
Ab3bd
输出样例#1：
2

倚窗倾听风吹雨

1. #include<iostream>
   
2. #include<cstdio>
   
3. using namespace std;
   
4. int i,j,n,f[2000][2000],ans;
   
5. char c1[2000],c2[2000];
   
6. int main()
   
7. {
   
8.     while(scanf("%s",c1)!=EOF)continue;
   
9.     while(c1[n++]!=0)continue;
   
10.     n--;
    
11.     for(i=0;i<n;i++)
    
12.         c2[i]=c1[n-i-1];
    
13.     for(i=1;i<=n;i++)
    
14.     {
    
15.         for(j=1;j<=n;j++)
    
16.         {
    
17.             if(c1[i-1]==c2[j-1])f[i][j]=f[i-1][j-1]+1;
    
18.             else f[i][j]=max(f[i-1][j],f[i][j-1]);
    
19.            /// cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
    
20.         }
    
21.     }
    
22.     /*for(i=0;i<n;i++)cout<<c2[i];
    
23.     cout<<endl<<n<<endl;
    
24.     cout<<f[n][n];*/
    
25.     ans=n-f[n][n];
    
26.     cout<<ans;
    
27.     return 0;
    
28. }
    

复制代码

walk_alone

1. #include <cstdio>
   
2. #include <cstring>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. int f[1001][1001];
   
6. int main()
   
7. {
   
8.         char a[2001],b[2001];
   
9.         scanf("%s",a+1);
   
10.         int len=strlen(a+1);
    
11.         for(int i=1;i<=len;i++)
    
12.                 b[len-i+1]=a[i];
    
13.         for(int i=1;i<=len;i++)
    
14.                 for(int j=1;j<=len;j++)
    
15.                         if(a[i]==b[j])
    
16.                                 f[i][j]=f[i-1][j-1]+1;
    
17.                         else
    
18.                                 f[i][j]=max(f[i][j-1],f[i-1][j]);
    
19.         printf("%d",len-f[len][len]);
    
20.         return 0;
    
21. }

复制代码

黄煦喆

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. string s1;
   
5. int a[1001][1001];
   
6. int main()
   
7. {
   
8.     cin>>s1;
   
9.     int len=s1.size();
   
10.     string s2=s1;
    
11.     reverse(s2.begin(),s2.end());
    
12.     s1=' '+s1;s2=' '+s2;
    
13.     for(int i=1;i<=len;i++)
    
14.         for(int j=1;j<=len;j++)
    
15.         if(s1[i]==s2[j])a[i][j]=a[i-1][j-1]+1;
    
16.     else a[i][j]=max(a[i-1][j],a[i][j-1]);
    
17.     cout<<len-a[len][len];
    
18.     return 0;
    
19. }
    

复制代码

张笑宇

1. #include<iostream>
   
2. using namespace std;
   
3. string s1,s2;
   
4. int l,i,j;
   
5. const int mx=1010;
   
6. int dp[mx][mx];
   
7. int main()
   
8. {
   
9.     cin>>s1;
   
10.     l=s1.size(),s2="";
    
11.     for (i=0;i<=l-1;i++) s2=s1[i]+s2;
    
12.     for (i=0;i<=l-1;i++)
    
13.         for (j=0;j<=l-1;j++) dp[i][j]=0;
    
14.     for (i=1;i<=l;i++)
    
15.         for (j=1;j<=l;j++)
    
16.     {
    
17.         if (s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
    
18.         else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    
19.         ///cout<<dp[i][j]<<" "<<i<<" "<<j<<endl;
    
20.     }
    
21.     ///cout<<s1<<endl<<s2<<endl;
    
22.     cout<<l-dp[l][l];
    
23.     return 0;
    
24. }
    

复制代码

张笑宇

最长公共子序列+反转字串