CF607B Zuma

link CodeForces

题意

Genos 最近在他的手机上下载了祖玛游戏。在祖玛游戏里，存在 $n$ 个一行的宝石，第 $i$ 个宝石的颜色是 $C_i$ 。这个游戏的目标是尽快的消灭一行中所有的宝石。 在一秒钟，Genos 能很快的挑选出这些有颜色的宝石中的一个回文的，连续的子串，并将这个子串移除。每当一个子串被删除后，剩余的宝石将连接在一起，形成一个新的行列。你的任务是：求出把整个宝石串都移除的最短时间。 让我们给你一个提示：如果一个串正着读或倒着读都一样，那么这个串（或子串）叫回文串。在我们这道题中，“回文”指这个宝石串中的第一个珠子的颜色等于最后一个珠子的颜色，第二个珠子的颜色等于倒数第二个珠子的颜色，等等。

解法

看到这种题面后，想法是搞区间dp或者记忆化搜索。当时我正在学区间dp，所以我用的方法是区间dp的方法。 我们设 $f(i,j)$ 是区间 $[i,j]$ 中消除该区间宝石串最短的时间。所以易得初始化 $f(i,i)=1$ 。 我们可以枚举区间长度， $i$ 为左端点， $j$ 为右端点，当满足区间 $[i,j]$ 是回文串时，知道了消除区间 $[i,j]$ 回文串所用的时间与消除区间 $[i+1,j-1]$ 回文子串的时间一样，我们可以得到第一个状态转移方程 $f(i,j)=\min(f(i,j),f(i+1,j-1)) (a_i=a_j)$ 。 在枚举区间长度后，我们还要枚举断点。易得 $f(i,j)=\min(f(i,j),f(i,k)+f(k+1,j))$ 。 我们发现 $a_i=a_j$ 状态转移方程式有些问题，当 $j=i+1$ 时 $f(i,i+1)=f(i+1,i)$ ，这时区间长度为 $0$ ，所以说我们要把长度为 $0$ 的区间初始化为 $1$ ，即 $f(i,i-1)=1$

代码

#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cctype>
typedef long long LL;
namespace FastIo{
    static char buf[100000],*p1=buf,*p2=buf,fw[100000],*pw=fw;
    #define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++
    inline void pc(const char &ch){
    	if(pw-fw==100000)fwrite(fw,1,100000,stdout),pw=fw;
    	*pw++=ch;
	}
    #define fsh fwrite(fw,1,pw-fw,stdout),pw=fw
    struct QIO{
    	char ch;
    	int st[40];
    	template<class T>inline void read(T &x){
    		x=0,ch=gc;
    		while(!isdigit(ch))ch=gc;
    		while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;}
		}
		template<class T>inline void write(T a){
			do{st[++st[0]]=a%10;a/=10;}while(a);
			while(st[0])pc(st[st[0]--]^48);
		}
	}qrw;
}
using namespace FastIo;
using std::min;
#define NUMBER1 500
#define P(A) A=-~A
LL f[NUMBER1+5][NUMBER1+5];
int a[NUMBER1+5];
signed main(){
	memset(f,0x7f7f,sizeof(f));
	int n;
	qrw.read(n);
	for(register int i(1);i<=n;P(i)){
		qrw.read(a[i]);
		f[i][i]=f[i][i-1]=1;
	}
	for(register int len(1);len<=n;P(len))
		for(register int i(1);i<n;P(i)){
			register int j=i+len;
			if(j>n)break;
			if(a[i]==a[j])f[i][j]=min(f[i][j],f[i+1][j-1]);
			for(register int k=i;k<j;P(k))f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
		}
	qrw.write(f[1][n]);
	fsh;
    exit(0);
    return 0;
}