石子合并
别人讲过太多了，蒟蒻就不说了。
Polygon
这题跟石子合并类似，只是多输出了个先清除哪条边可以使得值最大。
因为我们不确定先删那一条，我们就再复制一遍添到输入的结尾，就变成了 $2 \times N - 1$。
我们思考最大值是由哪些贡献的。
- 最大值与最大值运算。
- 最小值乘上最小值（因为当负数乘上负数时，会变为正数）。
那么最小值。
- 最大值乘上最小值（当最大值为正数时，反而会更小）。
- 最小值加上最
我们设 $f1_{i,j}$ 为以 $i$ 为左端点 $j$ 为右端点这个区间内的最大值， $f2_{i,j}$ 为最小值。
定义一个函数：
int deal(int x, int y, int op) {
if (op == 't') return x + y;
return x * y;
}
动态转移方程是
$$f1(i,j) = \max(deal(f1(k+1,j), f1(i,k),op_{k+1}),deal(f2(k + 1,j), f2(i,k),op_{k + 1}))$$
$$f2_(i,j) = \min(deal(f2(k+1,j), f2(i,k),op_{k+1}),deal(f1_(k + 1,j), f2_(i,k),op_{k + 1}))$$
最后我们去寻找以 $i$ 为起点的，长度为 $n$ 的最大值，如果等于最后答案，那么便输出，因为这样一定能删去第 $i$ 条边，得到最大值。
串折叠 Folding&秘密文件&[SCOI2003] 字符串折叠
三倍经验，快乐。
就拿第一个讲。
我们设 $dp[i][j]$ 表示字符串中 $s[i\sim j]$ 折叠后的最小长度。
它可以有两种方式转移而来：
- 由两段子串折叠后的最小长度加起来。
- 以一段子串为循环元，然后出折叠后的长度。
我们通过：
for (int i = l; i + k <= r; i++) {
if (s[i] != s[i + k]) return 0;
}
return 1;
去找到循环元。
于是：
$$dp[i][j] = min(dp[i][k] + dp[k+1][j], dp[i][k] + 2 + m[(j - i + 1) \div (k - i + 1])$$
其中，$m$ 数组时每个数的位数。因为 $s[i\sim k]$ 为循环元，那么就会有 $(j - i + 1) \div (k - i + 1)$ 个循环元，再加上括号的个数，便为折叠后的个数。
我们还要求出字符串是什么，那么在转移时加上即可。
上代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 200;
int n, f[N][N], m[N];
string s, ans[N][N];
bool check(int l, int r, int k) {
for (int i = l; i + k <= r; i++) {
if (s[i] != s[i + k]) return 0;
}
return 1;
}
string shu(int x) {//求出数字的字符串
string res = "";
while (x) {
res = char(x % 10 + '0') + res;
x /= 10;
}
return res;
}
int main() {
for (int i = 1; i <= 9; i++) m[i] = 1;
for (int i = 10; i < 100; i++) m[i] = 2;
for (int i = 100; i <= 199; i++) m[i] = 3;
while (cin >> s) {
n = s.size();
s = " " + s;
for (int l = 0; l < n; l++) {//区间DP
for (int i = 1; i + l <= n; i++) {
int j = l + i;
f[i][j] = l + 1;
ans[i][j] = s.substr(i, l + 1);//初始化
for (int k = i; k < j; k++) {
if (f[i][j] > f[i][k] + f[k + 1][j]) {
f[i][j] = f[i][k] + f[k + 1][j];
ans[i][j] = ans[i][k] + ans[k + 1][j];//求出字符串
}
else if (f[i][j] == f[i][k] + f[k + 1][j]) {
ans[i][j] = max(ans[i][j], ans[i][k] + ans[k + 1][j]);//如果个数相同，找到字典序最大的一项。
}
}
for (int k = i; k < j; k++) {
int len = k - i + 1;
if ((l + 1) % len == 0 && check(i, j, len)) {
string sub = shu((l + 1) / len) + '(' + ans[i][k] + ')';//以 s[i~k] 为循环元的字符串
if (f[i][j] > f[i][k] + 2 + m[(l + 1) / len]) {
f[i][j] = min(f[i][j], f[i][k] + 2 + m[(l + 1) / len]);
ans[i][j] = sub;
}
else if (f[i][j] == f[i][k] + 2 + m[(l + 1) / len]) ans[i][j] = max(ans[i][j], sub);//如果个数相同，找到字典序最大的一项。
}
}
}
}
cout << ans[1][n] << '\n';
}
return 0;
}