天天看點

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 }      
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\n", my_vec1.size() - lcf(my_vec1, my_vec2));
44     }
45     return 0;
46 }      

Aspire to inspire until I expire