欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

[UVA - 11584] Partitioning by Palindromes dp预处理

程序员文章站 2022-04-01 18:49:11
s...

题目链接:Partitioning by Palindromes

题意

给你一个字符串,让你把它划分成尽量少的回文串,最后输出回文串个数。

题解

字符串长度为1000,可以用dp去入手。
dp[i]:字符0~i划分成最少回文串的个数。
状态转移:dp[i]=min(d[j]+1,judge(j+1,i))(judge[i][j]ij{dp[i]=min{(d[j]+1,judge(j+1,i)) (judge[i][j]是判断字符串i~j是否为回文串}}
状态O(n)个,决策O(n)个,状态转移O(n)个。
总的时间复杂度为O(n3){O(n^3)},很明显不合题意。

状态和转移我们无法改变,我们唯一能做的就是处理决策。我们可以预处理判断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])
我们可以预处理O(n2){O(n^2)}的时间复杂度判断出s[i,j]是否为回文子串,然后再O(n2){O(n^2)}的时间复杂度求解。

代码

#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

相关标签: dp入门