动态规划

题目可以很容易看出来是区间型动态规划，但是传统的类似“定义$dp[l][r]$表示删除$s[l,...,r]$所需要的最少操作次数”看上去并不好得出状态转移方程。所以需要做一些小小的转换。

可以发现，如果一个子串是回文子串，那么我们仅需一次就可以删除它。所以可以定义：$dp[l][r]$表示将$s[l,...,r]$变成回文子串所需要的最少操作次数。

1. 如果$s[l]==s[r]$，那么$dp[l][r]=dp[l+1][r-1]$，不需要操作
2. 同时，有$dp[l][r]=min(dp[l][r],d[l][k]+dp[k+1][r]+1),l\le k\lt r$。表示子串$s[l,...,r]$变成回文串，是两个回文子串$s[l,...,k]$和$s[k+1,...,r]$中删除1个变成的。

最终答案为$dp[1][n]+1$

时间复杂度为$O(TN^3)$。

看上去会超时，但是题目存在$\sum{n}\le 3000$的约束，所以远远达不到时间复杂度的上限。

代码

C++

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int n,T;
char s[505];
int dp[505][505];

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%s",s+1);
        n=strlen(s+1);
        memset(dp,0x3f,sizeof dp);
        for(int i=1;i<=n;++i){
            dp[i][i]=0;
            dp[i+1][i]=0;
        }
        for(int len=2;len<=n;++len){
            for(int l=1,r;l+len-1<=n;++l){
                r = l+len-1;
                if(s[l]==s[r]){
                    dp[l][r]=dp[l+1][r-1];
                }
                for(int k=l;k<r;++k){
                	dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+1);
				}
//                printf("dp[%d][%d] = %d\n",l,r,dp[l][r]); 
            }
        }
        printf("%d\n",dp[1][n]+1);
    }

    return 0;
}

会员可通过查看《已通过》的提交记录来查看其他语言哦~

题目描述

小红有一个长度为$n$的字符串,这个字符串由26个小写字母组成。

小红可以对这个字符串进行多次操作,每次操作可以把该字符串中一段连续的回文子串删除(单个字符也属于回文串),删除后剩下的串会拼在一起,请问最少需要多少次操作可以将这个字符串删光

输入描述

第一行,包含一个正整数 $T(1 \le T\le 20)$代表测试数据的组数

对于每组测试数据,仅有一行,代表这个字符串。

$(1\le n\le 500)$保证$\sum n$ 不超过 3000

输出描述

对于每组数据输出一行整数,代表小红在进行最少多少次操作后,可以将这个字符串删光

样例

输入

3
mwapd
tvuvv
yxxml

输出

5
3
4