P2135 方块消除

· · 题解 

     区间dp

2135
a[i]第i个数
b[i]第i个数有几个
s[i]从1到i一共有多少个格子（前缀和

首先我们们读题可以发现，这是一个区间的题，而且这很不像贪心，于是我们考虑dp，首先也是最明显的就是一个区间嘛，所以一定要有l，r。
然而我们可以发现这不够，因为我们想让后面连在一起消除，所以我们还要维护一个后面有几个和a[r],一样的数，这样更好转移，dp[l][r][k]表示在l到r这段区间，后面有k个和a[r]一样的数，全部删掉后的最大得分，这样我们就想办法把他们一起消除使得分最高。
先是我们为他们赋值。
枚举k（0~s[n]-s[r]）//剩下一共s[n]-s[r]个数
dp[l][r][k]=dp[l][r-1][0]+(b[r]+k)(b[r]+k);
然后枚举k（分割点a[k]==a[r]）
j(0~s[n]-s[r])
dp[l][r][k]=max(dp[l][r][k],dp[l][k][b[r]+j]+dp[k+1][r-1][0]. //区间加区间。 

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;

int n;

int a[50001],b[50001],s[50001];

int dp[200][200][200];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&b[i]);
        s[i]=s[i-1]+b[i];
    }
    for(int i=0;i<=n;i++)
    {
        for(int l=1;l<=n;l++)
        {
            int r=i+l;
            if(i+l>n)
            break;
            for(int k=0;k<=s[n]-s[r];k++)
            dp[l][r][k]=dp[l][r-1][0]+(b[r]+k)*(b[r]+k);
            for(int k=l;k<r;k++)
            for(int j=0;j<=s[n]-s[r];j++)
            {
                if(a[k]==a[r])
                dp[l][r][j]=max(dp[l][r][j],dp[l][k][b[r]+j]+dp[k+1][r-1][0]);
            }
        }
    }
    printf("%d",dp[1][n][0]);
    return 0;
}