题解 P2135 【方块消除】

· · 题解

题解 - P2135

题目意思

题目传送门

\mathrm{Sol}

区间dp

一道模拟赛的题目，然后一直在推 f_{l,r} 为 [l,r] 区间的最大贡献的转移一直没搞出来，后来发现由于删除一块会使得两端颜色相同的块合并就很难转移，于是我们多记录一维 f_{l,r,s} 表示 [l,r] 区间内以及在 (r,n] 这段区间紧接 r 的与 col_r 相同的个数为 s。

转移我们分两种情况转移：

$(2)$ 我们在 $[l,r)$ 这段区间里找一个 $i$ 使得 $col_i=col_r$，这时候我们是删掉 $(i,r)$ 这段区间使得 $i,r$ 合并。此时转移为：$f_{l,r,s}=\max\limits_{i=l}^{r-1}(f_{l,r,s},f_{l,i,len_r+s}+f_{i+1,r-1,0})$。 这样时间复杂度： $O(n^4)

\mathrm{Code}

#include <bits/stdc++.h>
#define For(i,a,b) for ( int i=(a);i<=(b);i++ )
#define Dow(i,b,a) for ( int i=(b);i>=(a);i-- )
#define GO(i,x) for ( int i=head[x];i;i=e[i].nex )
#define mem(x,s) memset(x,s,sizeof(x))
#define cpy(x,s) memcpy(x,s,sizeof(x))
#define YES return puts("YES"),0
#define NO return puts("NO"),0
#define GG return puts("-1"),0
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;

struct IO
{
    #define MAXSIZE (1 << 20)
    #define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE],*p1,*p2;
    char pbuf[MAXSIZE],*pp;
    IO():p1(buf),p2(buf),pp(pbuf){}
    inline char gc() {
        return getchar();
        if (p1==p2) p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin);
        return p1==p2?' ':*p1++;
    }
    inline bool blank(char ch) {return ch==' '||ch =='\n'||ch == '\r'||ch == '\t';}
    template <class T>
    inline void read(T &x)
    {
        register double tmp=1;register bool sign=0; x=0;
        register char ch=gc();
        for (;!isdigit(ch);ch=gc()) if(ch=='-') sign=1;
        for (;isdigit(ch);ch=gc()) x=x*10+(ch-'0');
        if (ch=='.') for (ch=gc();isdigit(ch);ch=gc()) tmp/=10.0,x+=tmp*(ch-'0');
        if (sign) x=-x;
    }
    inline void read(char *s)
    {
        register char ch=gc();
        for (;blank(ch);ch=gc());
        for (;!blank(ch);ch=gc()) *s++=ch;
        *s=0;
    }
    inline void read(char &c) {for(c=gc();blank(c);c=gc());}
    template<class t> inline void write(t x){
        if(x<0) putchar('-'),write(-x);
        else{if(x>9) write(x/10);putchar('0'+x%10);}
    }
} io;

const int mod=1e9+7;
const int mo=998244353;
const int N=2e2+5;

int n,m,col[N],len[N],pre[N],f[N][N][N],ans;

int main()
{
    io.read(n);
    For(i,1,n) io.read(col[i]);
    For(i,1,n) io.read(len[i]),pre[i]=pre[i-1]+len[i];
    For(l,1,n) for ( int L=1;L+l-1<=n;L++ ) 
    {
        int R=L+l-1;
        For(i,0,pre[n]-pre[R]) f[L][R][i]=f[L][R-1][0]+sqr(len[R]+i);
        For(i,L,R-1) For(j,0,pre[n]-pre[R]) if(col[i]==col[R])
        f[L][R][j]=max(f[L][R][j],f[L][i][len[R]+j]+f[i+1][R-1][0]);
    }
    io.write(f[1][n][0]);
    return 0;
}