[刷题笔记] CF607B Zuma

Problem

貌似还是某场cf div1的B

Description

一个数组\(a\)，每次可以消掉其中的一个回文串，求至少经过几次操作能消掉字符串\(s\)？

Solution

我们发现本题满足大区间包含小区间的特性，即通过小区间可以推出大区间，符合区间dp。

考虑状态转移，枚举一个区间\(l,r\)，如果\(a_l=a_r\)则答案肯定是\(f_{l+1,r-1}\)也就是她前面的，因为此时\(a_l\)和\(a_r\)符合回文，不需要额外消，可以和前面\(f_{l+1,r-1}\)一起消。

剩下的就套用普通的区间dp板子即可。注意初始化\(f_{i,i}=1\)，每一个数都需要一次消除。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 1000
#define INF 0x3f3f3f3f
using namespace std;
int n;
int a[N];
int f[N][N];
int main()
{
    memset(f,INF,sizeof(f));
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) f[i][i] = 1;
    for(int len=2;len<=n;len++)
    {
        for(int l=1;l+len-1<=n&&l<=n;l++)
        {
            int r = l+len-1;
            if(a[l] == a[r]) 
            {
                if(l+1 == r) f[l][r] = 1;
                else f[l][r] = f[l+1][r-1];
            }
            for(int k=l;k<r;k++) 
            {
                f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]);
            }
        }
    }
    cout<<f[1][n]<<endl;
    return 0;
}