『输出方案的区间DP』Folding

本文主要是介绍『输出方案的区间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] = n u m + 2 + m i n l e n$
num表示循环节个数，minlen表示最小循环节的长度。
此时 $g [i] [j] = n u m +^{'} (^{'} + m i n l e n +^{'})^{'}$

这道题对我们的启示就是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;
}