CF607B Zuma
不知道为什么你谷会评蓝，这不是很基础的区间DP吗。
题意简述
消除回文子串的最小次数。
思路
对于区间\([i,j]\)，如果它是回文的，那么消除它所需的次数是\(1\)。
如果它不是回文的，但是\(a[i]==a[j]\)，那么当区间\([i+1,j-1]\)被消除到只剩下一个回文串时，它就变成了回文串。因此消除它所需次数可以为\(dp[i+1][j-1]\)，也可以把它分成若干段分开消除。取其中最小值。
如果它不是回文的，且\(a[i]!=a[j]\)，那么想消除它只能分开消除。
综上所述，我们得到了一个状态转移方程：
\[\large dp[i][j]=\min(dp[i+1][j-1],dp[i][k]+dp[k+1][j](i\le k<j)(a[i]==a[j]) \]\[\large dp[i][j]=\min(dp[i][k]+dp[k+1][j](i\le k<j)(a[i]!=a[j]) \]这样我们容易得到它的边界条件：
\[\large dp[i][i]=1 \]当然，可以在\(i>j\)时设\(dp[i][j]=1\)。
实现
初始将\(dp\)数组设为\(\inf\)。
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
dp[i][j]=1;
for(int l=2;l<=n;l++)
for(int i=1;i+l-1<=n;i++)
{
int j=i+l-1;
if(a[i]==a[j])
dp[i][j]=dp[i+1][j-1];
for(int k=i;k<j;k++)
dp[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
}
printf("%d",f[1][n]);