上海计算机学会2024年10月月赛C++乙组T3回文子串（二）
发布时间
阅读量：
阅读量
回文子串（二）
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个仅包含小写字母的字符串 s，每次你可以选出一个回文子串，并将其删去；此时余下的字符串会自动前后拼接成一个新的字符串。
请问，最少需要多少多少步才能将原字符串全部删完？
输入格式
输入共一行，一个字符串 s
输出格式
输出共一行， 一个正整数表示答案
数据范围
设 ∣s∣ 为给定字符串 s 的长度
- 对于 30% 的数据， 1≤∣s∣≤10
- 对于 60% 的数据， 1≤∣s∣≤100
- 对于 100% 的数据， 1≤∣s∣≤1000
样例数据
输入:
iai
输出:
1
输入:
iaa
输出:
2
解析：动态规划，
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int dp[1005][1005];//dp[i][j]表示字串从第i个字符到第j个字符最少几次删空
int main() {
cin >> s;
n = s.length();
s = " " + s;
for(int i = 1; i <= n; i++) {
dp[i][i] = 1;
}
for(int i = n; i >= 1; i--) {//循环起点
for(int j = i + 1; j <= n; j++) {//循环终点
dp[i][j] = dp[i + 1][j] + 1;//默认单独删除第i个字符
//将i到j分割为i到k，k+1到j，枚举k，取删除两段的和的最小值
for(int k = i + 1; k <= j; k++) {
if (s[i] == s[k]) {
//max(dp[i + 1][k - 1], 1)：若两端相等，则可以跟中间的一起删除
//若中间没有（为0）则需要单独删除（取1）
dp[i][j] = min(dp[i][j], max(dp[i + 1][k - 1], 1) + dp[k + 1][j]);
}
}
}
}
cout << dp[1][n];
return 0;
}
全部评论 (0)
还没有任何评论哟~