题意简述：
有 (n) 个石头排成一排，第 (i) 个石头的颜色是 (a_i)。
你可以选择一段连续的回文的子段，然后把它消去，剩下的石头会向中间靠近，把之前消去的石头的空隙补上。
问按照这样的规则，最少要几次把 (n) 个石头都消去。
( exttt{Data Range:} 1leq nleq500, 1leq a_ileq n。)
看到数据范围这么小，一眼想到区间 DP。
我们设 (dp_{i,j}) 表示消除区间 ([i, j]) 所要花费的最少次数。
一些简单的边界不难想到：
[egin{cases}
dp_{i,i}=1&\
dp_{i,i+1}=1&(c_i = c_{i+1})\
dp_{i,i+1}=2&(c_i
ot = c_{i+1})
end{cases}]
然后具体想一想怎么转移：
- 若 (c_i = c_{j})，那么很明显区间 ([i, j]) 可以和区间 ([i+1,j-1]) 一起消除，所以 (dp_{i,j}=dp_{i+1,j-1})。
- 若 (c_i ot = c_j)，那么枚举分割点 (k)，消除区间 ([i,j]) 就可以转化为消除区间 ([i,k]) 和 ([k+1,j])，所以 (dp_{i,j}=minlimits_{k=i}^{j-1}{dp_{i,k}+dp_{k+1,j}})。
代码就很好写了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int INF = 0x3f3f3f3f, N = 503;
int n, m;
int a[N];
int dp[N][N];
int main()
{
n = gi();
for (int i = 1; i <= n; i+=1) a[i] = gi();
memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= n; i+=1)
dp[i][i] = 1;
for (int i = 1; i < n; i+=1)
if (a[i] == a[i + 1]) dp[i][i + 1] = 1;
else dp[i][i + 1] = 2;
for (int len = 3; len <= n; len+=1)
for (int i = 1; i + len - 1 <= n; i+=1)
{
int j = i + len - 1;
if (a[i] == a[j]) dp[i][j] = dp[i + 1][j - 1];
for (int k = i; k < j; k+=1)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
printf("%d
", dp[1][n]);
return 0;
}