nyoj 37-回文字符串(reverse, 动态规划， lcs)

37-回文字符串

内存限制:64MB 时间限制:3000ms Special Judge: No
accepted:10 submit:17

题目描述:

所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，比如"aba"。当然，我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你，给你一个字符串，可在任意位置添加字符，最少再添加几个字符，可以使这个字符串成为回文字符串。

输入描述:

第一行给出整数N（0<N<100）
接下来的N行，每行一个字符串，每个字符串长度不超过1000.

输出描述:

每行输出所需添加的最少字符数

样例输入:

1
Ab3bd

样例输出:

2

分析：
　　①、vector字符的插入用的是push_back(c); eg: vec1.push_back(c);
　　②、要求一个串至少加多少个字符成为回文字符串，可以通过将其反转后与原串求lcs(最大公共子串)；
　　③、将vector中的字符个数 - lcs即为所求；
　　④、字符串的反转，我们可以通过vector中的reverse
　　　　1、具体用法：reverse(vec1.begin(), vec1.end());
　　　　2、说明，酱紫将会将vec1中的数据从开始到结束的数据全部翻转最终结果复制到vec1中
　　
LCS(模板)：

 1 int lcs(vector<char> vec1, vector<char> vec2) // vec2是vec1的反转串
 2 {
 3     memset(dp, 0, sizeof(vec1));
 4     int len1 = vec1.size(), len2 = vec2.size(); // 当然这里的len1与len2是相等的
 5     for(int i = 1; i <= len1; ++ i)
 6     {
 7         for(int j = 1; j <= len2; ++ j)
 8         {
 9             if(vec1[i-1] == vec2[j-1]) 
10                 dp[i][j] = dp[i-1][j-1] + 1; // 用dp[i][j]来村vec1的前i - 1个串与vec2的前j - 1个串的最大公共子串
11             else
12                 dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
13         }
14     }
15     return dp[len1][len2];
16 }

C/C++代码实现（AC）：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <stack>
 7 #include <map>
 8 #include <queue>
 9 #include <set>
10 
11 using namespace std;
12 const int MAXN = 1010;
13 int dp[MAXN][MAXN];
14 
15 int lcf(vector<char> vec1, vector<char> vec2)
16 {
17     int len1 = vec1.size(), len2 = vec2.size();
18     memset(dp, 0, sizeof(dp));
19     for(int i = 1; i <= len1; ++ i)
20     {
21         for(int j = 1; j <= len2; ++ j)
22             if(vec1[i-1] == vec2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
23             else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
24     }
25     return dp[len1][len2];
26 }
27 
28 int main()
29 {
30     int t;
31     scanf("%d", &t);
32     while(t --)
33     {
34         vector<char> my_vec1, my_vec2;
35         char s[MAXN];
36         int len_s;
37         scanf("%s", s);
38         len_s = strlen(s);
39         for(int i = 0; i < len_s; ++ i)
40             my_vec1.push_back(s[i]); // vector类型的数据通过push_back插入数据
41         my_vec2 = my_vec1;
42         reverse(my_vec1.begin(), my_vec1.end()); //将数组my_vec1反转
43         printf("%d
", my_vec1.size() - lcf(my_vec1, my_vec2));
44     }
45     return 0;
46 }