华师一附中OI组

标题: P1435 回文字串 [打印本页]
作者: 倚窗倾听风吹雨    时间: 2018-7-15 09:00
标题: P1435 回文字串
https://www.luogu.org/problemnew/show/P1435

题目背景
IOI2000第一题

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

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

注：此问题区分大小写

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

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

输入输出样例
输入样例#1：
Ab3bd
输出样例#1：
2
作者: 倚窗倾听风吹雨    时间: 2018-7-15 09:00
  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    时间: 2018-7-27 21:45
  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. }
复制代码
作者: 黄煦喆    时间: 2018-7-28 16:18
  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. }
复制代码
作者: 张笑宇    时间: 2018-7-28 17:06
  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. }
复制代码
作者: 张笑宇    时间: 2018-7-28 17:07
最长公共子序列+反转字串
作者: ZMQ    时间: 2018-8-4 22:11
提示: 作者被禁止或删除 内容自动屏蔽



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2