Luogu3146 [USACO16OPEN]248

发布于 2019-09-21  201 次阅读


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;
}

朴实沉毅