『输出方案的区间DP』Folding

Problem

Bill试图通过折叠其中的重复子序列来紧凑地表示从“A”到“Z”的大写字母字符序列。

例如，表示序列AAAAAAAAAABABABCCD的一种方法是10（A）2（BA）B2（C）D。他通过以下方式正式定义了折叠的字符序列以及它们的展开变换： 包含从“A”到“Z”的单个字符的序列被认为是折叠序列。展开此序列会产生单个字符本身的相同序列。 如果S和Q是折叠序列，则SQ也是折叠序列。如果S展开到S’并且Q展开到Q’，则SQ展开到S’Q’。

如果S是折叠序列，则X（S）也是折叠序列，其中X是大于1的整数的十进制表示。如果S展开到S’，则X（S）展开到S’重复X倍。

根据这个定义，很容易展开任何给定的折叠序列。但是，比尔对逆向转型更感兴趣。他希望折叠给定的序列，使得得到的折叠序列包含尽可能少的字符数。

Dolution

我们设$f[i][j]$表示$[i,j]$的最小字符数，设$g[i][j]$表示$[i,j]$的反感。

显然对于区间$[i,j]$的答案，一定分为两部分：

• 由子区间转移过来;即两个子区间之和.可以得到：$$f[i][j]=f[i][k]+f[k+1][j].$$
  $$g[i][j]=g[i][k]+g[k+1][j]$$
• 单独对所有的循环节进行合并。此时暴力查找循环节即可。$$f[i][j]=num+2+minlen$$
  num表示循环节个数，minlen表示最小循环节的长度。
• 此时$g[i][j]=num{+}^{\prime }{(}^{\prime }+minlen{+}^{\prime }{)}^{\prime }$

这道题对我们的启示就是DP输出反感不一定要做完以后再递归查找，当答案序列不大时可以边做边记录。

代码如下：

#include <bits/stdc++.h>using namespace std;
const int N = 200;char a[N];
string g[N][N], t[N][N];
int f[N][N], c[N][N], pre[N][N], n;int find(int l, int r)
{
    for (int L=1;L<=r-l+1;++L) {
    if ((r-l+1) % L) continue; int flag = 1;for (int i=l;i<=r-L;++i) if (a[i] ^ a[i+L]) {
    flag = 0;break;}if (flag == 1) return L;}return 0;
}
//寻找最小循环节 string str(int x)
{
    int t = 0;int s[1000];string S;while (x > 0) s[++t] = x%10, x /= 10;for (int i=t;i;--i) S += s[i]+'0';return S;
}int main(void)
{
    freopen("folding.in","r",stdin);freopen("folding.out","w",stdout);cin >> a+1;n = strlen(a+1);for (int i=1;i<=n;++i) {
    f[i][i] = 1;g[i][i] = a[i];}for (int len=2;len<=n;++len)for (int i=1;i<=n-len+1;++i){
    int j = i+len-1;f[i][j] = INT_MAX;for (int k=i;k<j;++k) if (g[i][k].size() + g[k+1][j].size() < f[i][j])f[i][j] = g[i][k].size() + g[k+1][j].size(),g[i][j] = g[i][k] + g[k+1][j];int len = find(i, j);if (len == 0) continue;int num = (j-i+1) / len;string S = str(num) + '(' + g[i][i+len-1] + ')';if (S.size() < f[i][j]) f[i][j] = S.size(), g[i][j] = S;} cout<<g[1][n]<<endl;return 0;
}