cf 1132 F

区间dp。。

每次删一串相邻的一样的，问多少次删光。

感觉想的几乎是一样的怎么比赛时就过不了呢。。。一定是因为我挂机睡觉了

考虑l和r相等,l和l+1相等，r和r-1相等这三种情况就行了。。然后就是裸的区间dp。。

上紫计划再次流产.jpg

和bzoj1260一样的？

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N = 505;
 5 int dp[N][N];
 6 int n;
 7 string s;
 8 int min(int a,int b,int c){
 9     return min(a,min(b,c));
10 }
11 int main(){
12     ios::sync_with_stdio(false);
13     memset(dp,0x3f, sizeof(dp));
14     cin>>n>>s;
15     s="*"+s;
16     for(int i=1;i<=n;i++)
17         dp[i][i]=1;
18     for(int l=2;l<=n;l++){
19         for(int i=1;i<=n;i++){
20             int j = i+l-1;
21             if(j>n)break;
22             for(int k=i;k<j;k++){
23                 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
24             }
25             if(s[i]==s[j]){
26                 dp[i][j]=min(dp[i+1][j-1]+1,dp[i+1][j],dp[i][j-1]);
27             }
28             if(s[i]==s[i+1])
29                 dp[i][j]=min(dp[i][j],dp[i+1][j]);
30             if(s[j]==s[j-1])
31                 dp[i][j]=min(dp[i][j],dp[i][j-1]);
32         }
33     }
34     cout<<dp[1][n];
35 }

View Code