动态规划(划分成回文串,uva 11584)

时间:2021-12-15 11:11:09

对每个位子进行DP时要先初始化一下他的值,这是就要考虑到有没有在接下来的循环中没能考虑到的边界情况,如果有,就在这些没有考虑到的情况中选一个最优解最为初始值,情况很少,往往判断一下就OK。如果没有遗漏的情况,那就给他赋一个一定会被替换的值,比如求最小值,你就给他赋INF,求最大值,你就给他赋-1或-INF。但要保证这个值一定会被替换,而且不会被认为是某个正确的结果。


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

char str[1010];
bool is[1010][1010];
int dp[1010];

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(is,0,sizeof(is));
scanf("%s",str+1);
int len=strlen(str+1);
for(int i=1;i<=len;i++)
{
int l,r;
l=r=i;
is[l][r]=1;
while(l-1>=1&&r+1<=len&&str[l-1]==str[r+1])
{
l--;
r++;
is[l][r]=1;
}
}
for(int i=1;i<=len-1;i++)
{
int l=i;
int r=i+1;
if(str[l]==str[r]) is[l][r]=1;
else continue;
while(l-1>=1&&r+1<=len&&str[l-1]==str[r+1])
{
l--;
r++;
is[l][r]=1;
}
}
for(int i=1;i<=len;i++)
{
if(is[1][i]) dp[i]=1;
else dp[i]=i;
for(int j=1;j<i;j++)
if(is[j+1][i])
dp[i]=min(dp[i],dp[j]+1);
}
printf("%d\n",dp[len]);
}
return 0;
}