cf607 B. Zuma（区间dp，回文串）

题意：

给定数组，每次可以删除一个回文子段，求最少几次可以删完。

\(1\le n \le 500\)

思路：

\(f(l,r)\) 表示删除 \([l,r]\) 需要的最小次数。如果 \(a_l=a_r\)，那么 \(a_l\) 和 \(a_r\) 可以接到 \([l+1,r-1]\) 中的某个回文序列中，不需要额外代价。

特殊处理长度为2的子段

const int N = 505;
int n, a[N], f[N][N];

main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    memset(f, INF, sizeof f);
    for(int i = 1; i <= n; i++) f[i][i] = 1;
    for(int i = 2; i <= n; i++) if(a[i] == a[i-1]) f[i-1][i] = 1;

    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]) f[l][r] = min(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];
}