Luogu3146 [USACO16OPEN]248

[Problem](https://www.luogu.org/problemnew/show/P3146)

题意

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

题解

这个题很像[石子合并](https://www.luogu.org/problemnew/show/P1880)，也可以算是刚刚上手区间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

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int SIZE = 300 + 5;
 5 
 6 int n;
 7 int a[SIZE], f[SIZE][SIZE];
 8 
 9 inline int read()
10 {
11     char ch = getchar();
12     int f = 1, x = 0;
13     while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
14     while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
15     return x * f;
16 }
17 
18 int main()
19 {
20     n = read();
21     int ans = 0;
22     for (int i = 1; i <= n; i++) a[i] = read(), ans = std::max(ans, a[i]);
23     for (int i = 1; i <= n; i++) f[i][i] = a[i];
24     for (int len = 2; len <= n; len++)
25     for (int l = 1; l <= n - len + 1; l++)
26     {
27         int r = l + len - 1;
28         for (int k = l; k < r; k++)
29         {
30         if (f[l][k] == f[k + 1][r])
31             f[l][r] = std::max(f[l][r], f[l][k] + 1);
32         }
33         ans = std::max(ans, f[l][r]);
34     }
35     printf("%d", ans);
36     return 0;
37 }