0x53 区间DP

石子合并

题意：

合并两堆相邻石子的代价为两堆石子的质量和。将所有堆石子合并为 1 堆的最小代价。

解析：

长的区间一定由短区间转移，所以按区间长度划分阶段。枚举长区间的分割点进行转移

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 3e2+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int n;
int f[maxn][maxn];
int a[maxn], sum[maxn];int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];sum[i] = sum[i-1] + a[i];}memset(f, INF, sizeof(f));for(int i = 1; i <= n; i++)f[i][i] = 0;for(int len = 2; len <= n; len++){for(int st = 1; st <= n-len+1; st++){int ed = len+st-1;for(int k = st; k < ed; k++){f[st][ed] = min(f[st][ed], f[st][k]+f[k+1][ed]+sum[ed]-sum[st-1]);}}}cout << f[1][n];return 0;
}

多边形

题意：

一个多边形，边上是运算符 * 或 +，点上是数字。每次操作可以去掉一条边和两个顶点，产生一个新点，新点上的数字为删除的运算结果。

只剩一个点时，最大的数字。

解析：

先断环成链。因为数字可以为负，最大值不一定由最大值转移而来，但一定由最值转移。

所以令 $f_{k=0/1,i,j}$ 为区间 $[i, j]$ 合并成一个点的最值。 $k = 0$ 为最大值， $k = 1$ 为最小值。

然后同上题，枚举分割点进行转移。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 100+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int a[maxn], n;
int dp[2][maxn][maxn];
char op[maxn];
int cal(int a, int b, char ch){if(ch == 'x')return a * b;elsereturn a + b;
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i <= n; i++){cin >> op[i] >> a[i];op[n+i] = op[i]; a[i+n] = a[i];}memset(dp[0], -INF, sizeof(dp[0]));memset(dp[1], INF, sizeof(dp[1]));for(int i = 1; i <= n * 2; i++)dp[0][i][i] = dp[1][i][i] = a[i];for(int len = 2; len <= n; len++){for(int st = 1; st <= 2*n-len+1; st++){int ed = st+len-1;for(int k = st; k < ed; k++){for(int i = 0; i <= 1; i++){for(int j = 0; j <= 1; j++){dp[0][st][ed] = max(dp[0][st][ed], cal(dp[i][st][k], dp[j][k+1][ed], op[k+1]));dp[1][st][ed] = min(dp[1][st][ed], cal(dp[i][st][k], dp[j][k+1][ed], op[k+1]));}}}}}	vector<int> res;int maxx = -INF;for(int i = 1; i <= n; i++){int t = dp[0][i][i+n-1];if(t > maxx){res.clear();maxx = t;res.push_back(i);}else if(maxx == t)res.push_back(i);}cout << maxx << endl;for(auto x : res)cout << x << " ";return 0;
}

金字塔

题意：

一个树，每个点有一个颜色。按照dfs遍历这棵树会产生一个颜色序列。每到一个节点（无论是第一次进入还是返回），都会记录这个节点的颜色。除叶子节点，其余节点至少访问两次。

给定一个颜色序列，询问有多少种树的结构能产生这个序列。

解析：

区间DP+记忆化搜索

对以 $u$ 为节点的子树，产生的序列形如： $u-subtree_1-u-subtree_2-...-subtree_x-u$ ， $x$ 为 $u$ 的儿子个数。

可以将这棵树分为两部分： $u-subtree_1$ 和 $u-subtree_2-...-subtree_x-u$ 。设第二部分的起点位置为 $k$ ，则 $dpl,r+=dpl,k−1×dpk,rdp_{l,r} += dp_{l,k-1}\times dp_{k,r}$ 。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 3e2+10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9;
typedef pair<int, int> pii;ll dp[maxn][maxn];
char s[maxn];
ll dfs(int l, int r){if(l > r)return 0;else if(l == r)return 1;if(dp[l][r] != -1)return dp[l][r];ll &res = dp[l][r];res = 0;if(s[l] == s[r]){for(int k = l; k <= r; k++){res = (res + dfs(l+1, k-1) * dfs(k, r)) % mod;}}return res;
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> s+1;memset(dp, -1, sizeof(dp));cout << dfs(1, strlen(s+1));return 0;
}