CF 682D

• 真是蠢了好久…
  
  • @ 题意：最长公共子串，并且这个匹配对于s和t来说都是分割成k块子串（不能再多了），
  • 幸好k小的一比（k < 10），$n<10^3$。
  • @ dp[k][i][j][st == 0 or 1]表示s的前i个字符与t前j个字符在k划分下st == 1为连续，
  • 否则不连续的最大匹配个数。
  • st1的转移方式是显然只有当前 s[i] == t[j]时候才能转移，能转移过来的状态有很多，
  • 一定要想清楚再写，不然Debug到死。

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
const int maxn = 1107;
int n, m, z;
std::string s, t;
int dp[2][maxn][maxn][2];
void debug(int now, int st){
    std::cout << "    ";
    for(int i = 0; i < m; i ++) {
        std::cout << t[i] << ' ';
    }
    std::cout << "\n" <<n << m << "\n";
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            if(j == 1) std::cout << s[i - 1] << " : ";
            std::cout << dp[now][i][j][st] << ' ';
        }
        std::cout << "\n";
    }
    std::cout << std::endl;
}
int main()
{
    std::cin >> n >> m >> z;
    std::cin >> s;
    std::cin >> t;
    int now = 0, pre = 0, ans = 0;
    for(int k = 1; k <= z; k ++){
        now = pre ^ 1;
        memset(dp[now], 0, sizeof(dp[now]));
        for(int i = k; i <= n; i ++){
            for(int j = k; j <= m; j ++){
                dp[now][i][j][0] = std::max(dp[now][i - 1][j][0], dp[now][i][j - 1][0]);
                if(s[i - 1] == t[j - 1]){
                    dp[now][i][j][1] = std::max(std::max(dp[pre][i - 1][j - 1][0], dp[pre][i - 1][j - 1][1]), dp[now][i - 1][j - 1][1]) + 1;
                    dp[now][i][j][0] = std::max(dp[now][i][j][0], std::max(dp[pre][i - 1][j - 1][0], dp[pre][i - 1][j - 1][1]) + 1);
                }
                dp[now][i][j][0] = std::max(dp[now][i][j][0], dp[now][i][j][1]);
                ans = std::max(ans, std::max(dp[now][i][j][0], dp[now][i][j][1]));
            }
        }
        pre = now;
    }
    std::cout << ans << "\n";
}