文章目录
- P3146 [USACO16OPEN]248 G
- AC代码
P3146 [USACO16OPEN]248 G
本博客给出本题截图：
AC代码
代码解释：
这里的状态转移方程定义有一些特别，我们定义f[i][j]表示将[i, j]范围内完全合并后的分数最大值
所以我们带入到区间dp后的思路为，只有当我们的f[i][k] == f[k + 1][j]的时候，才可以进行状态转移，我们用res表示我们的最终答案，为什么最终答案不是f[1][n]？答：由于我们定义f[i][j]为完全合并，但是显然从[1, n]不是全部都能合并的，如果不能完全合并，那么显然会有f[1][n] == 0，故f[1, n]不是最终的解，而是需要不断的去更新res
代码：
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 250; int f[N][N]; int n, res; int s[N]; int main() { cin >>n; for (int i = 1; i <= n; i ++ ) { cin >> s[i]; f[i][i] = s[i]; } for (int len = 2; len <= n; len ++ ) for (int i = 1; i + len - 1 <= n; i ++ ) { int j = i + len - 1; for (int k = i; k < j; k ++ ) { if (f[i][k] == f[k + 1][j]) { f[i][j] = max(f[i][j], f[i][k] + 1); res = max(res, f[i][j]); } } } cout << res << endl; return 0; }
