题解 P3146 【[USACO16OPEN]248】

· · 题解

Problem

题意

有一列数字，对两两相邻的数字进行合并操作，其中合并的贡献是1，问最大的贡献。

题解

​ 这个题很像石子合并，也可以算是刚刚上手区间DP的经典题型吧

​ 首先考虑状态，区间DP的重要思想就是把小区间的贡献算出来，然后计给大区间使用，包含这种思想的有著名的线段树和树状数组，在这里不详细讲。所以我们不妨设 len 表示状态，为我们当前合并的区间长度。最开始我们的区间长度都是 1 ，之后在DP过程中枚举。

​ 之后考虑转移，按照套路，不妨设 l, r 表示当前区间的两个端点，f[l,r] 表示合并 [l,r] 区间的最大贡献。在 l,r 中间我们再枚举一个的断点 k ，表示在 len 长度的一个大区间内，有 [l,k] 这个区间，这是一个小区间，根据区间DP用小区间更新大区间的思想，那么我们的转移就是：f[l,r] = min(f[l][r], f[l][k])

​ 最后考虑一下初值，我们最开始这一个序列中的数都是一个一个来合并的，所以区间最开始的长度就是1，不妨在读入的时候就比较一下最大值。显而易见，f[i,i] = a[i]

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 300 + 5;

int n;
int a[SIZE], f[SIZE][SIZE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    n = read();
    int ans = 0;
    for (int i = 1; i <= n; i++) a[i] = read(), ans = std::max(ans, a[i]);
    for (int i = 1; i <= n; i++) f[i][i] = a[i];
    for (int len = 2; len <= n; len++)
    for (int l = 1; l <= n - len + 1; l++)
    {
        int r = l + len - 1;
        for (int k = l; k < r; k++)
        {
        if (f[l][k] == f[k + 1][r])
            f[l][r] = std::max(f[l][r], f[l][k] + 1);
        }
        ans = std::max(ans, f[l][r]);
    }
    printf("%d", ans);
    return 0;
}