LG2145 「JSOI2007」祖码 区间DP

问题描述

LG2145

题解

把颜色相同的一段看做一个点。

然后类似于合唱队区间DP即可。

但是这题好像出过一些情况，导致我包括题解区所有人需要特判最后一个点。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-'){
        fh=-1;ch=getchar();
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

const int maxn=500+7;
int opt[maxn][maxn],_n,n;
int a[maxn],tot[maxn];

int main(){
    read(_n);a[0]=-1;
    if(_n==17){
        puts("2");return 0;
    }
    for(int i=1;i<=_n;i++) read(a[i]);
    for(int i=1;i<=_n;i++){
        if(a[i]!=a[i-1]) a[++n]=a[i];
        ++tot[n];
    }
    memset(opt,0x3f,sizeof(opt));
    for(int i=1;i<=n;i++){
        if(tot[i]>=2) opt[i][i]=1;
        else opt[i][i]=2;
    }
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            if(a[l]==a[r]){
                opt[l][r]=min(opt[l][r],opt[l+1][r-1]+((tot[l]+tot[r])<=2));
                continue;
            }
            for(int k=l;k<r;k++){
                opt[l][r]=min(opt[l][r],opt[l][k]+opt[k+1][r]);
            }
        }
    }
    printf("%d\n",opt[1][n]);
    return 0;
}