Codeforces 607B
原题：CF607B Zuma
Genos recently installed the game Zuma on his phone. In Zuma there exists a line of n n n gemstones, the i i i -th of which has color ci c_{i} ci . The goal of the game is to destroy all the gemstones in the line as quickly as possible.
In one second, Genos is able to choose exactly one continuous substring of colored gemstones that is a palindrome and remove it from the line. After the substring is removed, the remaining gemstones shift to form a solid line again. What is the minimum number of seconds needed to destroy the entire line?
Let us remind, that the string (or substring) is called palindrome, if it reads same backwards or forward. In our case this means the color of the first gemstone is equal to the color of the last one, the color of the second gemstone is equal to the color of the next to last and so on.
题目描述
Genos最近在他的手机上下载了祖玛游戏。在祖玛游戏里，存在n个一行的宝石，第i个宝石的颜色是Ci 。这个游戏的目标是尽快的消灭一行中所有的宝石。 在一秒钟，Genos能很快的挑选出这些有颜色的宝石中的一个回文的，连续的子串，并将这个子串移除。每当一个子串被删除后，剩余的宝石将连接在一起，形成一个新的行列。你的任务是：求出把整个宝石串都移除的最短时间。 让我们给你一个提示：如果一个串正着读或倒着读都一样，那么这个串（或子串）叫回文串。在我们这道题中，“回文”指这个宝石串中的第一个珠子的颜色等于最后一个珠子的颜色，第二个珠子的颜色等于倒数第二个珠子的颜色，等等。 输入输出格式 输入格式：
第一行包含一个整数n(1<=n<=500) ——宝石串的长度。 第二行包含n个被空格分开的整数，第i(1<=i<=n) 个表示这行中第i个珠子的颜色。 输出格式：
输出一个整数，把这行珠子移除的最短时间。 (样例略) 说明：
在第一个例子中，Genos可以在一秒钟就把这行珠子全部移走。 在第二个例子中，Genos一次只能移走一个珠子，所以移走三个珠子花费他三秒。 在第三个例子中，为了达到2秒的最快时间，先移除回文串4 4,再移除回文串1 2 3 2 1。
思路：判断回文，做dp，f[i][j]表示i-j的这段区间所需要的最小值.
可以由中间两段或由一段消完的转移而来。
代码如下
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int n,a[100005],f[10005][10005];
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
f[i][j]=99999;
}
}
for(int i=0;i<=n;i++) f[i][i]=1;
for(int i=1;i<=n;i++){
if(a[i]==a[i+1]) f[i][i+1]=1;
else f[i][i+1]=2;
}
for(int i=2;i<=n;i++){
for(int j=1;j+i<=n;j++){
for(int k=j;k<i+j;k++){
f[j][i+j]=min(f[j][i+j],f[j][k]+f[k+1][i+j]);
}
if(a[j]==a[i+j]) f[j][i+j]=min(f[j][i+j],f[j+1][i+j-1]);
else f[j][i+j]=min(f[j][i+j],f[j+1][i+j-1]+2);
}
}
cout<<f[1][n]<<endl;
}