题解 P3146 [USACO16OPEN]248 G

ctq1999 · 2020-03-21 23:20:55 · 题解

题解

有 1\times n 可以想到区间dp，设 f[i][j] 为从 i 到 j 的可以合并得到的最大值。

初始f[i][i]=a[i] 。那么 f[i][j] 要从它的子区间转移过来。

if (f[i][k] == f[k + 1][j])
f[i][j] = max(f[i][k] + 1, f[i][j]);

其中 i，j 为当前要转移的区间，k 为此区间分成两个子区间的断点。

时间复杂度 O(n^3) 。

代码

#include <bits/stdc++.h>

#define MAXN 250

using namespace std;

int n, ans;

int a[MAXN], f[MAXN][MAXN];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        f[i][i] = a[i];
    }

    for (int len = 1; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; 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);
                    ans = max(f[i][j], ans);
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}

日拱一卒，功不唐捐