Codeforces 682D - Alyona and Strings

#DP #字符串
Published on 2016-06-25

题目地址

描述

给你两个长度为 n,m(n,m≤1000)n, m(n, m \le 1000) 的字符串 s,ts, t，再给出一个数 k(k≤10)k(k\le 10)，要求你给出 kk 个字符串 ，使得 s,ts, t 都能被表示为 ，允许 aia_i 为空。
请你最大化 ∣p1∣+∣p2∣+⋯∣pk∣\vert p_1\vert + \vert p_2\vert + \cdots \vert p_k \vert。

分析

这个形式，很像最长公共子序列，我们考虑 DP。
设 f[i][j][k]f[i][j][k] 为考虑 ss 的前 ii 个，tt 的前 jj 个，选出 kk 个相等的字符串的最大长度和。
我们考虑转移，f[i][j][k]f[i][j][k] 显然可以从 max(f[i−1][j][k],f[i][j−1][k])\max (f[i - 1][j][k], f[i][j - 1][k]) 转移。考虑 f[i][j][k]f[i][j][k] 与之前状态的异同点，如果 ，那么这个状态与 max(f[i−1][j][k],f[i][j−1][k])\max (f[i - 1][j][k], f[i][j - 1][k]) 没有任何不同。如果 si=tjs_i = t_j 的话，那么 f[i][j][k]f[i][j][k] 就可以从 f[i−1][j−1][k−1]f[i - 1][j - 1][k - 1] 转移。
再考虑 si=tjs_i = t_j 不做新字符串开头的情况，这时我们需要 si−1,tj−1s_{i - 1}, t_{j - 1} 也能对上，所以定义 g[i][j][k]g[i][j][k] 为在 f[i][j][k]f[i][j][k] 的基础上，强制使 sis_i 与 tjt_j 对上号。

那么转移十分清晰：

f[i][j][k]=max{f[i−1][j][k]f[i][j−1][k]max(f[i−1][j−1][k−1],g[i−1][j−1][k])+1si=tjf[i][j][k] = \max\begin{cases}f[i-1][j][k]\\f[i][j-1][k]\\\max(f[i -1][j-1][k-1], g[i-1][j-1][k]) + 1& s_i = t_j\end{cases}g[i][j][k]={max(f[i−1][j−1][k−1],g[i−1][j−1][k])+1si=tj−∞otherwise g[i][j][k] = \begin{cases}\max(f[i -1][j-1][k-1], g[i-1][j-1][k]) + 1 & s_i= t_j\\-\infty &otherwise\end{cases}

总结：在动态规划转移的过程中，要充分利用已经算过的状态，分析这个状态比以前的状态多什么，在多的地方下文章，而不是盲目的再做一次以前已经做过的决策。

代码

//  Created by Sengxian on 6/25/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Codeforces 682D DP + 字符串
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 1000 + 3, maxm = 1000 + 3, maxk = 10 + 1, INF = 0x3f3f3f3f;
int f[maxk][maxn][maxm], g[maxk][maxn][maxm];
char s[maxn], t[maxm];
int n, m, K;

int main() {
    memset(f, -INF, sizeof f);
    memset(g, -INF, sizeof g);
    memset(f[0], 0, sizeof f[0]);
    n = ReadInt(), m = ReadInt(), K = ReadInt();
    scanf("%s%s", s + 1, t + 1);
    for (int k = 1; k <= K; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j) {
                f[k][i][j] = max(f[k][i - 1][j], f[k][i][j - 1]);
                if (s[i] == t[j]) {
                    f[k][i][j] = max(f[k][i][j], f[k - 1][i - 1][j - 1] + 1);
                    f[k][i][j] = max(f[k][i][j], g[k][i - 1][j - 1] + 1);
                    g[k][i][j] = max(f[k - 1][i - 1][j - 1] + 1, g[k][i - 1][j - 1] + 1);
                } else g[k][i][j] = -INF;
            }

    printf("%d\n", f[K][n][m]);
    return 0;
}
BZOJ 3832 - [Poi2014]Rally