自动搬运

查看原文

来自洛谷，原作者为

	xiejinhao 人间总有一两风，填我十万八千梦

搬运于2025-08-24 21:45:47，当前版本为作者最后更新于2019-08-02 16:07:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$P3146$ $[USACO16OPEN]248$ 题解

这一篇题解送给初学区间$DP$的人，Dalao可以跳过啦

---

原题链接：$P3146 \ [USACO16OPEN]248$

• 我们分析下题意：题目要求我们可以将两个相邻的相同的数合并，每次合并得到的数是原来的数$+1$，求最后能得到的最大分值。

其实看到合并这一类操作，我们大多会想到区间$DP$。

区间$DP$最简单的状态就是$f[l][r]$表示从左端点$l$到右端点$r$其中合并能获得的最大分值（依题意改变）。

其转移也很简单，我们只需要在$[l,r)$内枚举一个断点，比如本题的转移方程就是$f[l][r]=max(f[l][r],f[l][k]+1)$，这里先不考虑边界。

那么，我们对于每一个左端点等于右端点的小区间，也就是单点，其初值肯定只有那一个点的值，所以边界有：$f[i][i]=a[i]$。

其余的边界都要看题意而定。

看完这些，是不是觉得区间$DP$有点简单了？但是，区间$DP$真正的难点在于其转移的条件和你如何想到这样转移。当然，在你题写多了之后自然就可以秒切这一类水题了。所以学好$DP$一定要多做题。

---

我们回到题目当中来

因为这题也没有其他的条件，所以状态还是$f[l][r]$，不需要其他维度来记录其他信息。

那么什么情况下才能转移呢？

很明显的，我们需要左边一段区间$f[l][k]$与右边一段区间$f[k+1][r]$的值相等才能转移，玩过$2048$的小伙伴应该也很清楚。其中$k$是我们枚举在$[l,r)$间的断点，至于为什么是左闭右开，因为右边一段区间是$f[k+1][r]$，总不能$k+1>r$吧。

所以转移方程：

$$f[l][r]=max(f[l][r],f[l][k]+1),if:f[l][k]=f[k+1][r] $$

但是，我们这样的转移方程是有漏洞的，我们可以用一组数据卡掉一些转移条件只有$f[l][k]=f[k+1][r]$的题解：

    Input:
        8
        2
        1
        1
        2
        4
        2
        3
        4


    Output:
        4
        
下面这些方便你复制： 8 2 1 1 2 4 2 3 4

如果你按上面那么写就会输出$5$，但由于数据太水，你那么写也是可以通过本题的。

为什么会出现错误呢？因为如果$f[l][k]=f[k+1][r]=0$，这时$f[l][r]$如果为$0$,其值会错误的被更新，然后就挂了。

因为$f[l][r]$我们还没有更新到，而$f[l][k]$与$f[k+1][r]$也没被更新，你说能不挂嘛？

那我们怎么解决呢？这个简单，我们只需在保证$f[l][k]=f[k+1][r]$的基础上加一句：$f[l][k]>0$即可。这样就有效的避免了$f[l][k],f[k+1][r]$未更新到就更新了$f[l][r]$的情况。

还有一个注意事项：最终答案不一定是$f[1][n]$，因为不是这个区间都能够合并在一起，我们在转移的时候记录一个最大值即可。

但如果整个区间没有任何一个小区间可以合并呢？这启示我们，答案的初值要赋为单点的最大值。

由于这一题我们单点的值再也用不到了，输入时直接输入$f[i][i]$即可。

$Code:$（建议你自己先写一写，不能急着看代码）

    #include<iostream>
    #include<cstdio>
    using namespace std;

    const int N = 250;
    int f[N][N];

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

        for(int len = 2; len <= n; len++) 
            for(int l = 1; l +len -1 <= n; l++) {
                int r = l + len - 1;
                for(int k = l; k < r; k++) 
                    if(f[l][k] == f[k + 1][r] && f[l][k]) {
                        f[l][r] = max(f[l][r], f[l][k] + 1);
                        ans = max(ans, f[l][r]);
                    }
            }

        printf("%d\n", ans);		
        return 0;
    } 

上面代码的时间复杂度为$O(N^3)$（应该是吧）

看完上面那些，相必你对区间$DP$有了更深一层的了解。

我们可以把区间$DP$进行一些总结：

1. 区间合并性

2. 注意转移条件

其余和普通$DP$应该时差不多的了。

---

难道你以为这一题就完了？

不，这一题还有其他$DP$做法。（我也不知道叫啥）

定义状态$f[i][k]$，表示第$i$个数合并得到数值为$k$，能够向右拓展的最右端点。因为是最右端点，所以这个$k$也一定是最大的。

那么我们怎么转移？我们学过线性$DP$应该都清楚。这次合并的价值是$+1$，那么上一次就是$k-1$，上一次的右端点就是$f[i][k-1]$，那么只要$f[i][k]$为$0$，即还没取到最优值，我们就可以转移：

$$f[i][k]=f[f[i][k-1]][k-1],if:f[i][k]=0$$

这个方程是比较难想的，也是比较复杂的，需要多思考。

那么如果$f[i][k]$不为$0$，说明数值$k$是可以合并到的，那么我们只需更新答案：

$$ans=max(ans,k),if:f[i][k]>0$$

我们枚举$k$即可。

但是哪一层循环放外面呢？我们应该要清楚，这里的$k$才是阶段，而$1-n$那一层才是决策。

那么$k$最大是多少，最小又是多少？我们来看$N∈[2,248]$，每一个数值$∈[1,40]$，那么$k$最大的情况就是$N=248$，所有数值都等于$40$，可以算出$k_{max}=47$，而最小呢？我们依次类推，$k_{min}=1$，即整个数列$N=1$，只有一个数$1$的情况。

转移边界:对于每一个数列的数值$a[i]$，$f[i][a[i]]=i+1$，即其最多向右合并到$i+1$。这个需要好好理解。

这样的$DP$基于倍增思想（我也不太清楚，倍增写得少）

$Code:$

    #include<iostream>
    #include<cstdio>
    using namespace std;

    const int N = 250, K = 50;
    int f[N][K];

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

        for(int k = 1;k <= 47; k++)
            for(int i = 1; i <= n; i++) {
                if (f[i][k] == 0) 
                    f[i][k] = f[f[i][k - 1]][k - 1];
                if (f[i][k]) 
                    ans=max(ans, k);
            }

        printf("%d\n", ans);
        return 0;
    }

现在我们已经把时间优化到了$O(47N)$了，感觉很优秀？

---

区间$DP$评测记录：区间$DP$作法

优化$DP$评测记录：优化$DP$做法

$End$