Codeforces Round #336 (Div. 2) D. Zuma

题意：给出一个数列，一次能消除一个回文数列，问最少多少次

思路：dp+搜索

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=505;
 4 
 5 int dp[N][N];
 6 int vis[N][N];
 7 int a[N];
 8 int n;
 9 
10 int dfs(int l,int r){
11     if(vis[l][r]) return dp[l][r];
12     vis[l][r]=1;
13     dp[l][r]=1000;
14     if(l>r) return dp[l][r]=0;
15     if(l==r) return dp[l][r]=1;
16     if(l==r-1){
17         if(a[l]==a[r]) return dp[l][r]=1;
18         else return dp[l][r]=2;
19     }
20     if(a[l]==a[r]) dp[l][r]=dfs(l+1,r-1);
21     for(int i=l;i<=r;i++){
22         dp[l][r]=min(dp[l][r],dfs(l,i)+dfs(i+1,r));
23     }
24     return dp[l][r];
25 }
26 
27 int main(){
28     cin>>n;
29     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
30     cout<<dfs(1,n)<<endl;
31 }