字符串类dp的题目总结

熟练掌握回文串吧，大致有dp或者模拟类的吧

①dp+预处理，懂得如何枚举回文串（一）

②dp匹配类型的题目（二）

③dp+预处理子串类型（三）

④字符串的组合数（四）

一：划分成回文串 UVA11584 紫书275 dp+预处理

题目大意：输入一个字符串，把他划分成尽量少的回文串，能划分成几个？

思路：定义dp[i]表示i之间最少能弄成几个回文串，然后枚举1~j(j < i)，然后在枚举j的时候判断目前是否为回文串，这样复杂度为n^3.因此我们提前用n^2判断好是否为回文串就行了。回文串的方法就是枚举中心，但是枚举中心也是有技巧的！

lrj老师的代码太牛了！！！第一次见到这么写的！！！具体看代码上的注释吧！！！

 // UVa11584 Partitioning by Palindromes

 // Rujia Liu

 // This code is slightly different from the book.

 // It uses memoization to judge whether s[i..j] is a palindrome.

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn =  + ;

 int n, kase, vis[maxn][maxn], p[maxn][maxn], d[maxn];

 char s[maxn];

 int is_palindrome(int i, int j) {

   if(i >= j) return ;

   if(s[i] != s[j]) return ;

   //p[i][j]定义的是i到j是否为回文串

   if(vis[i][j] == kase) return p[i][j];

   vis[i][j] = kase;//我去，还能这么玩，在dp的过程中预处理，然后用kase区分

   p[i][j] = is_palindrome(i+, j-);

   return p[i][j];

 }

 int main() {

   int T;

   scanf("%d", &T);

   memset(vis, , sizeof(vis));

   for(kase = ; kase <= T; kase++) {

     scanf("%s", s+);

     n = strlen(s+);

     d[] = ;

     for(int i = ; i <= n; i++) {

       d[i] = i+;

       for(int j = ; j < i; j++)

         if(is_palindrome(j+, i)) d[i] = min(d[i], d[j] + );

     }

     printf("%d\n", d[n]);

   }

   return ;

 }

然后我的for循环和lrj老师的不一样

 //看看会不会爆int!数组会不会少了一维！

 //取物问题一定要小心先手胜利的条件

 #include <bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define ALL(a) a.begin(), a.end()

 #define pb push_back

 #define mk make_pair

 #define fi first

 #define se second

 const int maxn =  + ;

 char atlas[maxn];

 int dp[maxn];

 bool p[maxn][maxn], vis[maxn][maxn];

 bool dfs(int i, int j){

     if (i == j || j < i) return true;

     if (atlas[i] != atlas[j]) return false;

     if (vis[i][j]) return p[i][j];

     vis[i][j] = true;

     p[i][j] = dfs(i + , j - );

     return p[i][j];

 }

 int main(){

     int t; cin >> t;

     while (t--){

         memset(vis, , sizeof(vis));

         scanf("%s", atlas + );

         int len = strlen(atlas + );

         for (int i = ; i <= len; i++){

             for (int j = ; j < i; j++){

                 p[i][j] = dfs(j, i);

             }

         }

         memset(dp, 0x3f, sizeof(dp));

         dp[] = ;

         for (int i = ; i <= len; i++){

             dp[i] = dp[i - ] + ;//我定义目前这个字符单独组成回文串

             for (int j = ; j <= i; j++){

                 if (p[i][j]){

                     dp[i] = min(dp[i], dp[j - ] + );

                 }

             }

         }

         printf("%d\n", dp[len]);

     }

     return ;

 }

学习之处：回文串有两种，一种是abba，另一种是cbabc。然后如何枚举这两种本来是应该要分类讨论的，我的想法是枚举i-j，然后用n^2的想法

二：括号序列 UVA1626 紫书278

题目大意：给你几个合法的串的定义，只包含()[]这四个符号，加上多少的(、)、[、]能使给定的串变成一个合法的串

思路：定义dp[i][j]表示从i~j成功匹配所需要添加的最少的符号的个数使之变成合法的串。

首先我们根据dfs来，可以发现，如果是dfs(i, j)，我们要尝试在每一种i~j中进行分割，然后如果i和j是一个合法的串，那么就直接dfs(i-1, j-1)，不然就进行分割，然后记得，当最后只有一个符号的时候就假定要再加一个字符即可。

//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

const int inf = 0x3f3f3f3f;

const int maxn =  + ;

char s[maxn];

int dp[maxn][maxn];//从最右边i开始，到j匹配成功的最小的数目

bool match(int i, int j){

    if (s[i] == '(' && s[j] == ')') return true;

    if (s[i] == '[' && s[j] == ']') return true;

    return false;

}

void display(int i, int j){

    if (i == j) {

        if (s[i] == '(' || s[i] == ')') printf("()");

        else printf("[]");

        return ;

    }

    int ans = dp[i][j];

    if (match(i, j) && ans == dp[i + ][j - ]){

        printf("%c", s[i]);

        display(i + , j - );

        printf("%c", s[j]);

        return ;

    }

    for (int k = i; k <= j - ; k++){

        if (ans == dp[i][k] + dp[k + ][j]){

            display(i, k); display(k + , j);

            return ;

        }

    }

}

void readline(char* S) {

  fgets(S, maxn, stdin);

}

int main(){

    int T;

    readline(s); sscanf(s, "%d", &T); readline(s);

    while (T--){

        readline(s);

        int n = strlen(s) - ;

        for (int i = ; i <= n; i++){

            dp[i][i] = ;

        }

        for (int i = n - ; i >= ; i--){

            for (int j = i + ; j <= n; j++){

                dp[i][j] = inf;

                if (match(i, j)) dp[i][j] = min(dp[i][j], dp[i + ][j - ]);

                for (int k = i; k <= j - ; k++){//如果从k=i+1开始枚举的话，就需要我下面的两句话,但是弊端就是输出的时候要多很多的条件。不过从i开始枚举的话就不需要了

                    //if (match(i, k)) dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j]);

                    //if (match(k, j)) dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k + 1][j - 1]);

                    ///上面两句话有没有无所谓，因为你的j是会枚举到你这些列举的情况的

                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + ][j]);

                }

            }

        }

        display(, n);

        printf("\n");

        if(T) printf("\n");

        readline(s);

        //printf("%d\n", dp[0][n]);

    }

    return ;

}

学习之处：定义的学习，dp边界的找寻通过dfs来进行的，如何路径输出

三：http://codeforces.com/contest/477/problem/C codeforces 272 div1 C

题目大意：给你字符串s和p，从s删除0~|s|个字符，最多能形成多少个不重叠的字串p

思路：定义dp[i][j]表示前i个字符删除j个，定义cal(i)表示从第i个开始往前数，删除几个才能组合成一个子串p。

 //看看会不会爆int!数组会不会少了一维！

 //取物问题一定要小心先手胜利的条件

 #include <bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define ALL(a) a.begin(), a.end()

 #define pb push_back

 #define mk make_pair

 #define fi first

 #define se second

 const int maxn =  + ;

 char s[maxn], p[maxn];

 int lens, lenp, pos;

 int dp[maxn][maxn];//对当前位置i，删除j个能产生的最大匹配数

 int cal(int ps){

     int lp = lenp;

     int cnt = ;

     for (int i = ps; i >= ; i--){

         if (s[i] == p[lp]){

             lp--;

             if (lp == ){

                 pos = i;

                 return cnt;

             }

         }

         else cnt++;

     }

 }

 int main(){

     scanf("%s", s + ); lens = strlen(s + );

     scanf("%s", p + ); lenp = strlen(p + );

     for (int i = lenp; i <= lens; i++){

         int cnt = cal(i);

         for (int j = ; j < i; j++){

             dp[i][j] = max(dp[i][j], dp[i - ][j]);

             if (j >= cnt && pos -  >= j - cnt){

                 dp[i][j] = max(dp[i][j], dp[pos - ][j - cnt] + );

             }

         }

     }

     for (int i = ; i <= lens; i++){

         printf("%d%c", dp[lens][i], i == lens ? '\n' : ' ');

     }

     return ;

 }

四：http://codeforces.com/contest/476/problem/B codeforces 272 div2 B

题目大意：给你两个串，串1是由+或-组合而成，串二是由+、-、?组合而成的。？可以随便改变成+或-，问有多少的概率能使得两个串的+和-数目相等

思路：先求出串1串二中的+-？的数目，然后让串一的+-减去串二的+-，如果小于0就直接概率为0，反之进行dp即可。定义dp[i][j]，表示一共有i+j个？，生成i个+，j个-。

 //看看会不会爆int!数组会不会少了一维！

 //取物问题一定要小心先手胜利的条件

 #include <bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define ALL(a) a.begin(), a.end()

 #define pb push_back

 #define mk make_pair

 #define fi first

 #define se second

 const int maxn =  + ;

 char s1[maxn], s2[maxn];

 double dp[maxn][maxn];

 int id(char c){

     if (c == '+') return ;

     if (c == '-') return ;

     if (c == '?') return ;

 }

 int main(){

     scanf("%s%s", s1, s2);

     int len = strlen(s1);

     for (int i = ; i < len; i++){

         s1[i] = id(s1[i]);

         s2[i] = id(s2[i]);

     }

     sort(s1, s1 + len);

     sort(s2, s2 + len);

     int t10 = upper_bound(s1, s1 + len, ) - lower_bound(s1, s1 + len, );

     int t11 = upper_bound(s1, s1 + len, ) - lower_bound(s1, s1 + len, );

     int t20 = upper_bound(s2, s2 + len, ) - lower_bound(s2, s2 + len, );

     int t21 = upper_bound(s2, s2 + len, ) - lower_bound(s2, s2 + len, );

     int t22 = upper_bound(s2, s2 + len, ) - lower_bound(s2, s2 + len, );

     t10 -= t20, t11 -= t21;

     if (t10 <  || t11 < ){

         printf("0.000000000000\n");

         return ;

     }

     double ans = ;

     dp[][] = 1.0;

     for (int i = ; i <= t22; i++){//有i个

         for (int j = ; j <= i; j++){//有j个+

             int l = i - j;

             if (j == ) dp[j][l] = dp[j][l - ] * 0.5;

             else if (l == ) dp[j][l] = dp[j - ][l] * 0.5;

             else dp[j][l] = max(dp[j - ][l] * 0.5 + dp[j][l - ] * 0.5, dp[j][l]);

         }

     }

     printf("%.12f\n", dp[t10][t11]);

     return ;

 }

五：

六：

七：

巴特西

字符串类dp的题目总结

最新文章

热门文章