题目来源于《挑战程序设计竞赛》，题目涉及的算法只对应相关章节 （不一定是最优解的，思路写的有点简陋）

例题1 编辑距离 传送门

题意:
编辑距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

思路:
dp[i][j]：所有将a中的前i个字母变成 b中前j个字母的集合的操作次数
对a中的第i个字母操作，分为以下四种操作
1. 在该字母之后添加: dp[i][j] = dp[i][j-1] + 1
2. 删除该字母: dp[i][j] = dp[i-1][j] + 1
3. 替换该字母: dp[i][j] = dp[i-1][j-1] + 1
4. 啥也不做(对应结尾字母相同): dp[i][j] = dp[i-1][j-1]

代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
char s1[N], s2[N];
int dp[N][N];

int edit_distance(char s1[], char s2[], int n, int m)
{
    for (int i = 1; i <= n; i++) dp[i][0] = i;
    for (int i = 1; i <= m; i++) dp[0][i] = i;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
        }
    return dp[n][m];
}

int main()
{
    cin >> s1 + 1;
    cin >> s2 + 1;
    int n = strlen(s1 + 1);
    int m = strlen(s2 + 1);

    cout << edit_distance(s1, s2, n, m);
}

例题2 禁止字符串

题意:
考虑只由’A’,’G’,’C’,’T’四种字符组成的DNA字符串。给定一个长度为K的字符串S。请计算长度恰好为n 且不包含 S的宇符串的个数。输出个数 mod 10009 后的结果。

思路:
trans[i][j]：在S[1…i]添加字符cho[j]后（新串T）, 满足 T的后缀 和 S的前缀 相等的最大长度
dp[i][j]：当前构造字符串P长度为i，满足𝑃[𝑖 −𝑗+1…𝑖]=𝑆[1…𝑖]的方案数

可得到如下转移方程：
设 ne = trans[i][j], 若 ne 合法（即 ne != k, k = |S|） dp[i+1][ne] += dp[i][j]

代码:

//禁止字符串 
#include <bits/stdc++.h>

using namespace std;

const int K = 110;
const int N = 10010;
const int C = 5;
const int mod = 10009;

int n, k;
string cho = "AGCT", s;

//trans[i][j]:当前已经匹配i个字符,添加字符cho[j]后,匹配的字符个数
int trans[K][C];
//dp[i][j]:当当前字符串长度为i,状态j结尾的方案数
int dp[N][K];

int main()
{
    cin >> n >> k;
    cin >> s;

    //预处理trans
    memset(trans, 0, sizeof trans);
    for (int i = 0; i < k; i++)
    {
        string tmp = s.substr(0, i);
        for (int j = 0; j < 4; j++)
        {
            string cur = tmp + cho[j];
            while (s.substr(0, cur.length()) != cur)
                cur = cur.substr(1);
            trans[i][j] = cur.length();
        }
    }

    //计算dp
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < k; j++)
            for (int c = 0; c < 4; c++)
            {
                int ne = trans[j][c];
                if (ne == k) continue;
                dp[i + 1][ne] = (dp[i + 1][ne] + dp[i][j]) % mod;
            }

    //计算总方案数
    int tot = 0;
    for (int i = 0; i < k; i++) 
        tot = (tot + dp[n][i]) % mod;
    cout << tot << endl;

    return 0;
}

例题3 DNA repair 传送门

题意:
考虑只由’A’,’G’,’C’,’T’四种字符组成的DNA字符串。给定一个原字符串s,和n个禁止模式字符串P1,P2…Pn。请修改宇符串s,使得其中不包含任何禁止模式。每次修改操作只能将S中的某个字符修改为其他字符。如果不存在这样的修改，请输出－1,否则，输出所需的最少修改回数。

思路:
考虑从左向右修改，以修改到的位置和对应的后缀状态进行动态规划

后缀状态表示方法：
先求出𝑃[1]…𝑃[𝑁]所有字符串的前缀串
以样例2为例，前缀串Q[1…K]为{“A”, “"T” ,”𝑇𝐺”}
为了避免重复，去重，每个前缀串的下标作为对应的后缀状态
对每个Q[i]，判断Q[i]的后缀中是否含有禁止串

状态转移数组trans[i][j] ：
与例题2的做法类似，添加字符后，反复删除第一个字符， 直到等于某个状态的字符串，即为转移到的状态

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

const int N = 55;
const int S = 1010;

int n, cas;
string s, p[N], cho = " AGCT";
bool flag[S];
int trans[S][5], dp[S][S];

int main()
{
    ios::sync_with_stdio(false);

    while (cin >> n && n)
    {
        for (int i = 1; i <= n; i++)
        {
            cin >> p[i];
            p[i] = " " + p[i];
        }
        cin >> s; s = " " + s;

        vector<string>pre;
        pre.push_back(" ");
        for (int i = 1; i <= n; i++)
            for (int j = 1; j < p[i].length(); j++)
            pre.push_back(" " + p[i].substr(1, j));
        stable_sort(pre.begin(), pre.end());
        pre.erase(unique(pre.begin(), pre.end()), pre.end());
        int m = (int)pre.size() - 1;

        for (int i = 0; i <= m; i++) flag[i] = 1;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
            {
                int lens = pre[i].length(), lent = p[j].length();
                if (lens >= lent && pre[i].substr(lens - lent + 1) == p[j].substr(1))
                {
                    flag[i] = 0;
                    break;
                }
            }

        for (int i = 0; i <= m; i++)
            for (int j = 1; j <= 4; j++)
            {
                string ne = pre[i] + cho[j];
                while (true)
                {
                    int pos = lower_bound(pre.begin(), pre.end(), ne) - pre.begin();
                    if (pos <= m && pre[pos] == ne)
                    {
                        trans[i][j] = pos;
                        break;
                    }
                    ne = " " + ne.substr(2);
                }
            }

        int lens = (int)s.length() - 1;
        for (int i = 0; i <= lens; i++)
            for (int j = 0; j <= m; j++)
            dp[i][j] = 0x3f3f3f3f;
        dp[0][0] = 0;
        for (int i = 0; i < lens; i++)
        {
            for (int j = 0; j <= m; j++)
            {
                if (dp[i][j] == 0x3f3f3f3f) continue;
                for (int k = 1; k <= 4; k++)
                {
                   int st = trans[j][k];
                   if (flag[st] == 0) continue;

                   if (s[i + 1] == cho[k]) dp[i + 1][st] = min(dp[i + 1][st], dp[i][j]);
                   else dp[i + 1][st] = min(dp[i + 1][st], dp[i][j] + 1);
                }
            }
        }

        int mi = 0x3f3f3f3f;
        for (int i = 0; i <= m; i++) mi = min(mi, dp[lens][i]);
        if (mi == 0x3f3f3f3f) mi = -1;
        printf("Case %d: %d\n", ++cas, mi);
    }

    return 0;
}

习题1 Easy Problem 传送门

题意:
给你一个字符串s，每个位置的字符都有一个删除的代价。现在可以删除一定量的字符使得新字符串不包含子序列”hard”（可以不连续），求最小代价。

思路:
dp[i][j]:当前处理位置为i, 包含t.subtr(1, i)子序列的最大权值和

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int n, fare[N];
char s[N], t[10] = " hard";
//dp[i][j]:当前处理位置为i, 包含t.subtr(1, i)子序列的最大权值和
ll dp[N][5];

int main()
{
    scanf("%d", &n);
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i++) scanf("%d", &fare[i]);

    ll sum = 0;
    for (int i = 1; i <= n; i++) sum += fare[i];

    for (int i = 1; i <= n; i++)
    {
        if (s[i] == 'h')
        {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]) + fare[i];
            dp[i][2] = dp[i - 1][2] + fare[i];
            dp[i][3] = dp[i - 1][3] + fare[i];
        }
        else if (s[i] == 'a')
        {
            dp[i][0] = dp[i - 1][0] + fare[i];
            dp[i][1] = dp[i - 1][1];
            dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]) + fare[i];
            dp[i][3] = dp[i - 1][3] + fare[i];
        }
        else if (s[i] == 'r')
        {
            dp[i][0] = dp[i - 1][0] + fare[i];
            dp[i][1] = dp[i - 1][1] + fare[i];
            dp[i][2] = dp[i - 1][2];
            dp[i][3] = max(dp[i - 1][2], dp[i - 1][3]) + fare[i];
        }
        else if (s[i] == 'd')
        {
            dp[i][0] = dp[i - 1][0] + fare[i];
            dp[i][1] = dp[i - 1][1] + fare[i];
            dp[i][2] = dp[i - 1][2] + fare[i];
            dp[i][3] = dp[i - 1][3];
        }
        else
        {
            dp[i][0] = dp[i - 1][0] + fare[i];
            dp[i][1] = dp[i - 1][1] + fare[i];
            dp[i][2] = dp[i - 1][2] + fare[i];
            dp[i][3] = dp[i - 1][3] + fare[i];
        }
    }

    ll ma = 0;
    for (int i = 0; i < 4; i++) ma = max(ma, dp[n][i]);
    printf("%lld\n", sum - ma);

    return 0;
}

附
本人不太会写博客，若有错误，敬请指出，有点丑见谅