bzoj 1032: [JSOI2007]祖码Zuma

/**************************************************************    Problem: 1032    User: lxy8584099    Language: C++    Result: Accepted    Time:148 ms    Memory:2008 kb****************************************************************/ /*    区间DP     相同的颜色缩成一堆 记录其左端点和右端点    不要忘记最后一堆的R为n。。。     初始化 如果左端点=右端点 则需要两个同色球        否则一个就够了    dp[i][j]表示 消去第i堆到第j堆需要的最少珠子（注意是堆！     转移显然有 dp[i][j] =min{ dp[i][k] + dp[k+1][j] }     但是遇到消去后 左右能继续消去的要进行判断处理 */#include<cstdio>#include<cstring>#define min(a,b) ((a>b)?(b):(a))using namespace std;const int N=550;int dp[N][N],n,top,col[N],L[N],R[N];void Init(){    scanf("%d",&n);    for(int i=1,x;i<=n;i++)    {        scanf("%d",&x);        if(i==1||x!=col[top])            col[++top]=x,L[top]=i,R[top-1]=i-1;    } R[top]=n; // 不要忘记。。 }void Solve(){    memset(dp,0x3f,sizeof(dp));    for(int i=1;i<=top;i++)         if(L[i]==R[i]) dp[i][i]=2;        else dp[i][i]=1; //预处理长度为 1 的堆     for(int l=2;l<=top;l++) // 枚举现在处理堆的长度     {        for(int i=1,j=i+l-1;i<=top-l+1;++i,j=i+l-1) // 枚举区间左端点        {            for(int k=i;k<j;k++) // 枚举dp中间点                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);            if(col[i]==col[j]&&i+1<=j-1)     // 如果左端点 右端点颜色相同 就可以考虑让它们自己消失             {                if(L[i]==R[i]&&L[j]==R[j])                     dp[i][j]=min(dp[i][j],dp[i+1][j-1]+1);                // 左右都只有一个 就需要还加一个                 else dp[i][j]=min(dp[i][j],dp[i+1][j-1]);                // 否则就可以自己消失             }           }             }    printf("%d\n",dp[1][top]);}int main(){    Init();    Solve();    return 0;}