luogu P2135 方块消除 |dp

题目描述

Jimmy最近迷上了一款叫做方块消除的游戏。游戏规则如下：n个带颜色方格排成一列，相同颜色的方块连成一个区域（如果两个相邻方块颜色相同，则这两个方块属于同一区域）。为简化题目，将连起来的同一颜色方块的数目用一个数表示。

例如，9 122233331表示为

4 1 2 3 1

1 3 4 1

游戏时，你可以任选一个区域消去。设这个区域包含的方块数为x，则将得到x^2个分值。方块消去之后，其余的方块就会竖直落到底部或其他方块上。而且当有一列方块被完全消去时，其右边的所有方块就会向左移一格。Jimmy希望你能找出得最高分的最佳方案，你能帮助他吗？

输入格式

第一行包含一个整数m(1<=m<=50)，表示同颜色方块区域的数目。第二行包含m个数，表示每个方块的颜色（1到m之间的整数）。

输出格式

仅一个整数，即最高可能得分。

---

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=50005;
#define int long long
int a[N],b[N],s[N],dp[205][205][205],sum[N],n;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)scanf("%lld",&b[i]),s[i]=s[i-1]+b[i];
    for(int i=0;i<=n;i++)
    for(int l=1;l+i<=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]);
    }
    cout<<dp[1][n][0]<<endl;
}