模板区间 dp
- 一个长 \(n(n \le 248)\) 的序列，选择数列中两个相邻且相等的元素，删去其中一个元素并使另一个元素的值 \(+1\)，求数次操作后数列中的最大值
- 将这看做是合并的过程
- \(dp_{i, j}\) 表示区间 \([i, j]\) 和为一个答案的取值，这里的取值其实是唯一的，所以可以之间判断
- 对于每个 \(dp_{i, j}\) 找到一个合法的 \(mid(i \le mid < r)\)，使得 \(dp_{i, m} = dp_{m + 1, j}\)，那么 \(dp_{i, j} = dp_{i, m} + 1\)
点击查看代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
const int MAXN = 300 + 3, MAXX = 502;
int n;
int a[MAXN];
int dp[MAXN][MAXN];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
int ANS = 0;
memset(dp, -1, sizeof(dp));
for(int i = 1; i <= n; i++){
cin >> a[i], ANS = max(ANS, a[i]), dp[i][i] = a[i];
}
for(int l = 2; l <= n; l++){
for(int i = n - l + 1; i >= 1; i--){
int j = i + l - 1;
for(int m = i; m < j; m++){
if(dp[i][m] != -1 && dp[m + 1][j] != -1 && dp[i][m] == dp[m + 1][j]){
dp[i][j] = dp[i][m] + 1;
ANS = max(ANS, dp[i][m] + 1);
}
}
}
}
cout << ANS;
return 0;
}
dp 的转移会有多余、重复的操作
- 对于这一题，\(dp_{i, j}\) 有两种转移
- 一种可以直接 \(dp_{i, j} = dp_{i, m} + dp_{m+1, j}\)
- 另一种可能会出现合并操作，那么你其实只需要判断 \(a_i\) 和 \(a_j\) 是否有相同
- 如果那个合并的串在中间，那么一定可以枚举到另一个 \(m\) 使得答案直接覆盖这个串
点击查看代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
const int MAXN = 300 + 3;
int n, m;
int a[MAXN], b[MAXN];
int dp[MAXN][MAXN];
int main() {
//ios::sync_with_stdio(0), cin.tie(0);
cin >> n, m = 0;
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
for(int x = 0; x <= n; x++) dp[i][j] = 1e9;
}
}
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= n; i++){
if(i == 1 || a[i] != a[i - 1]){
b[++m] = a[i];
}
}
for(int i = 1; i <= m; i++){
dp[i][i] = 1;
}
for(int l = 2; l <= m; l++){
for(int i = 1; i <= m - l + 1; i++){
int j = i + l - 1;
for(int m = i; m < j; m++){
dp[i][j] = min(dp[i][j], dp[i][m] + dp[m + 1][j] - (b[i] == b[j]));
}
}
}
cout << dp[1][m];
return 0;
}