[UVA - 11584] Partitioning by Palindromes dp预处理
程序员文章站
2022-04-01 18:49:11
s...
题目链接:Partitioning by Palindromes
题意
给你一个字符串,让你把它划分成尽量少的回文串,最后输出回文串个数。
题解
字符串长度为1000,可以用dp去入手。
dp[i]:字符0~i划分成最少回文串的个数。
状态转移:
状态O(n)个,决策O(n)个,状态转移O(n)个。
总的时间复杂度为,很明显不合题意。
状态和转移我们无法改变,我们唯一能做的就是处理决策。我们可以预处理判断s[i,j]是否为回文串。
现在问题转化为:给你一个字符串,让你判断字符串的任意一个子字符串是否为回文串。
记得前面做过的合并回文子串。
我们设judge[i][j]:s[i,j]的最长回文子串的长度,判断s[i,j]是否为回文子串只需判断judge[i][j]==j-i+1即可。
状态转移
s[i]==s[j]:judge[i][j]=judge[i+1][j-1]+2
else:judge[i][j]=max(judge[i][j-1],judge[i+1][j])
我们可以预处理的时间复杂度判断出s[i,j]是否为回文子串,然后再的时间复杂度求解。
代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
//extern "C"{void *__dso_handle=0;}
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define lowbit(x) x&-x
const double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=1e5+10;
const int maxm=100+10;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
char s[1005];
int dp[1005];
int judge[1005][1005];
int main()
{
int t; scanf("%d",&t);
while(t--)
{
scanf("%s",s+1);
int n=strlen(s+1);
memset(judge, 0, sizeof(judge));
for(int i=1;i<=n;i++) judge[i][i]=1;
for(int j=1;j<=n;j++)
for(int i=j-1;i>=1;i--)
{
if(s[i]==s[j]) judge[i][j]=judge[i+1][j-1]+2;
else judge[i][j]=max(judge[i][j-1],judge[i+1][j]);
}
dp[0]=0;
for(int i=1;i<=n;i++) dp[i]=inf;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
{
if(judge[j+1][i]==i-j) dp[i]=min(dp[i], dp[j]+1);
else dp[i]=min(dp[i],dp[j]+i-j);
}
printf("%d\n",dp[n]);
}
}
本文地址:https://blog.csdn.net/weixin_44235989/article/details/108181286
下一篇: python中的django是做什么的