题目描述

难度分:$1900$

输入长度$\leq 500$的字符串$s$，包含大小写英文字母。输入$k(1 \leq k \leq |s|)$。

每次操作，你可以把一个$s[i]$改成任意字符。把$s$分割为至多$k$个非空子串，要求每个子串都是回文串，最少要修改多少次？

第一行，输出最少修改次数。

第二行，输出修改后的字符串，并用+表示分割位置，详见样例。

如果有多种分割方案，输出其中任意一种。

输入样例$1$

abacaba
1

输出样例$1$

0
abacaba

输入样例$2$

abdcaba
2

输出样例$2$

1
abdcdba

输入样例$3$

abdcaba
5

输出样例$3$

0
a+b+d+c+aba

输入样例$4$

abacababababbcbabcd
3

输出样例$4$

1
abacaba+babab+bcbabcb

算法

这周简直是专项训练，灵茶和$LeetCode$每日一题保持高度同步，全是些回文的DP题目。

划分型DP

这个题的主体框架是一个划分型DP，但要正常进行划分型DP的话还需要一个区间DP的预处理。为了方便，让字符串的索引从$1$开始。

状态定义

$dp[i][k]$表示把长度为$i$的前缀划分为$k$个回文串所需要的最小操作次数，在这个定义下答案就是$dp[n][K]$。

状态转移

如果是空串，就只有一个$dp[0]][0]=0$是合法状态，因为空串只能$0$次操作划分成$0$个回文串。枚举$k \in [1,K]$，$i \in [1,n]$，我们考虑最后一段回文子串$[j,i]$的左端点$j \in [1,i]$，那么将$[1,i]$划分为$k$个回文串就是将$[1,j-1]$划分成$k-1$个回文串的代价$dp[j-1][k-1]$，加上最后一段$[j,i]$变成回文串的代价$cost[j][i]$，状态转移方程为$dp[i][k]=min_{j \in [1,i]}dp[j-1][k-1]+cost[j][i]$。

区间DP

现在问题就在于$cost[j][i]$怎么来的？这又是一个经典的区间DP。先从小到大枚举区间长度，然后枚举区间的左端点。

状态定义

$cost[l][r]$表示将子串$[l,r]$变成回文的最少操作次数。

状态转移

如果$s[l]=s[r]$，那么将$[l,r]$变成回文的代价就是将$[l+1,r-1]$变成回文的代价（注意长度为$2$时的边界情况），状态转移方程为$cost[l][r]=cost[l+1][r-1]$。如果$s[l] \neq s[r]$，就还要操作一次让两者相等，所以状态转移方程为$cost[l][r]=1+cost[l+1][r-1]$。

有了$cost$数组，就可以对上面的划分型DP进行$O(n)$的转移了。

根据DP矩阵构造一个合法方案

接下来先计算出最小操作次数$minop$，以及这个操作次数对应的分割出的子串个数$k$，把$minop$先输出。

然后从$n$开始从后往前找出所有的子串，给定指针$r=n$。如果$dp[l-1][k-1]+cost[l][r]=minop$，说明应该把子串$[l,r]$划分出来，然后指针$r$跳到$l-1$位置，$minop=minop-cost[l][r]$继续把前面的子串找出来，直到找全$k$个子串。把这$k$个串转为回文，再用+连接起来输出即可。

复杂度分析

时间复杂度

状态数量是$O(nk)$的，状态转移时需要枚举最后一个串的起始位置，时间复杂度为$O(n)$，因此整个算法的时间复杂度为$O(n^2k)$。至于预处理出$cost$，双重循环遍历$l$和$r$，时间复杂度为$O(n^2)$。以及后续通过$dp$矩阵求一个合法的方案，本质上就是在$s$串上面跳，所跳之处就是分割出的子串端点，其实也就是跳完了整个$s$串，并不会走回头路，因此时间复杂度为$O(n)$，这两个过程都不是瓶颈。

空间复杂度

空间消耗主要在于$dp$矩阵和$cost$矩阵，它们都是$O(n^2)$级别的空间，因此整个算法的额外空间复杂度为$O(n^2)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 510;
int cost[N][N], dp[N][N];

string get(string& s) {
    int l = 0, r = s.size() - 1;
    while(l < r) {
        if(s[l] != s[r]) {
            s[l] = s[r];
        }
        l++, r--;
    }
    return s;
}

int solve(string s, int K) {
    int n = s.size();
    memset(cost, 0, sizeof(cost));
    for(int len = 2; len <= n; len++) {
        for(int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            if(len == 2) {
                cost[l][r] = s[l - 1] != s[r - 1];
            }else {
                cost[l][r] = (s[l - 1] != s[r - 1]) + cost[l + 1][r - 1];
            }
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    for(int k = 1; k <= K; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                dp[i][k] = min(dp[i][k], dp[j - 1][k - 1] + cost[j][i]);
            }
        }
    }
    int minop = 0x3f3f3f3f;
    int k = 0;
    for(int i = 1; i <= K; i++) {
        if(dp[n][i] < minop) {
            minop = dp[n][i];
            k = i;
        }
    }
    cout << minop << endl;
    vector<string> partitions;
    int r = n;
    while(k > 0) {
        string term;
        for(int l = r; l >= 1; l--) {
            term.push_back(s[l - 1]);
            if(dp[l - 1][k - 1] + cost[l][r] == minop) {
                reverse(term.begin(), term.end());
                partitions.push_back(term);
                minop -= cost[l][r];
                r = l - 1;
                break;
            }
        }
        k--;
    }
    reverse(partitions.begin(), partitions.end());
    string ans;
    for(string part: partitions) {
        ans += get(part);
        ans.push_back('+');
    }
    ans.pop_back();
    cout << ans << endl;
}

int main() {
    int k;
    string s;
    cin >> s >> k;
    solve(s, k);
    return 0;
}