UVA11584
https://www.luogu.org/problemnew/show/UVA11584
暑假开始刷lrj紫/蓝书DP题
这几天做的一道
思路
预处理出所有的回文串是否存在前提 如果是j~i是回文串方程 f[i]=min(f[i],f[j-1]+1);
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
# define maxn 1010
int n,len;
int s[maxn][maxn];
//s[i][j]表示i到j是否是回文串
char st[maxn];
//字符串
int f[maxn];
void judge()
{
for(
int i=
1;i<=len;i++
)
{
s[i][i]=
1;
//每个字符自己是一个回文串
if(st[i]==st[i+
1])
//判断与他后面的是不是回文串
s[i][i+
1]=
1;
//去掉了偶数中心有两个的麻烦
}
for(
int i=len;i>=
1;i--
)
for(
int j=i+
1;j<=len;j++
)
{
if(st[i]==st[j]&&s[i+
1][j-
1])
s[i][j]=
1;
//如果相等且中间的是回文串
//那么他也是回文串
}
}
int main()
{
cin>>
n;
while(n)
{
memset(f,0x7f,
sizeof(f));
//初始化为最大值
memset(s,
0,
sizeof(s));
n--
;
scanf("%s",st+
1);
//从1开始存比较方便
st[
0]=
'0';
//设第0位为0 不然len为0
len=strlen(st+
1);
//长度
judge();
//判断回文串
f[
0]=
0;
//边界条件
for(
int i=
1;i<=len;i++
)
{
for(
int j=i;j>=
1;j--
)
{
if(s[j][i])
//如果j到i是回文串
//仔细看循环方式 注意是j到i
f[i]=min(f[i],f[j-
1]+
1);
}
}
printf("%d\n",f[len]);
//答案存在f[len]中
}
}
View Code
转载于:https://www.cnblogs.com/BrokenString/p/9424934.html
相关资源：JAVA上百实例源码以及开源项目
