P2135 题解

· · 题解

题意：

给定 m 接下来两行两个长为 m 的序列，第一行代表的是 m 个不同的区间的颜色，第二行代表的是 m 个区间的长度。同颜色的方块每次可以一起消除，设消除了 x 个，那么得分就是 x^2 消除后余下的序列会自动合并，直至序列为空，求最大得分。

分析：

首先， 双倍积分 传送门。二者大同小异了，个人觉得按照链接里的题来看会更清晰易懂，所以我们接下来默认按输入转化成实际的序列，再进行操作。

观察题意，合并序列，加分，最大值，联想一下合并石子，是不是区间 DP 的样子就出来了。 但是我们发现，这题不能直接令 dp_{(i,j)}=\max(dp_{i,k} + dp_{k+1,j}) 这样的转移，因为考虑到合并当前的小区间之后，可能新填充进来的是同色的，那么就得不偿失了，这显然是不行的。

考虑枚举最后一个方块消掉的时候，假设我们当前的区间是 [i,j] ，有两种可能：直接消掉他或者留着他和左边拼起来消掉。接下来考虑较难的第二种情况，那么我们不妨令 p 为从 j 同色向左最远的位置， q 为 p 左边 j 的颜色第一次出现的位置（我们此时讨论的是 i j 不同色，否则不会这样）。好了，那么现在有一点是可以确定下来的，就是我们一定要消掉 [q+1,p-1] 这一区间，因为留着它也不会更优。至此，我们终于引出了本题的核心的核心，第三维状态： dp(i,j,k) 表示原序列的右边再拼上 k 个颜色与右端点 j 相同的方块。

决策的过程就是要么直接删去该节点，要么就去找 p q 进行转移，详见代码。

本题真的很难，感性理解吧。

#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cctype>
#include<vector>
#include<string>
using namespace std;
int t,n,a[550],dp[550][550][100],dis[550]; 
int main(){

    int cnt = 0;

    scanf("%d",&cnt);
    int b[cnt+5];
    for(int i=1;i<=cnt;++i)scanf("%d",b+i);
    for(int x,i=1;i<=cnt;++i){
        scanf("%d",&x); 
        while(x--)a[++n]=b[i];
    //转换一下 
    }
    for(int i=n;i;--i)
        for(int j=i+1;j<=n;++j)
            if(a[i] == a[j])dis[i]++;//节点i右边有多少个颜色相同的预处理，其实就是第三维的状态上限 
    for(int i=n;i;--i)//倒叙O，因为是考虑后面带多少个同色的，从后往前来才行 
        for(int j=i;j<=n;++j){
            for(int k=i;k<j;++k)
                if(a[k] == a[j])//同色的点 
                    for(int l = 0;l <= dis[k];++l)//转移 
                        dp[i][j][l] = max(dp[i][j][l],dp[k+1][j-1][0] + dp[i][k][l+1]);//中间区间的贡献加上左边区间拼上l个同色的贡献 
            for(int p=0;p<=dis[j];++p)
                dp[i][j][p] = max(dp[i][j][p],dp[i][j-1][0] + (p+1)*(p+1));//不考虑内部同色，直接带上右边同色的贡献                        
        }
    printf("%d\n",dp[1][n][0]);//区间1，n拼上0个同色就是最大值 

}