UVA 10739 String to Palindrome（DP)
|
In this problem you are asked to convert a string into a palindrome with minimum number of operations. The operations are described below:
Here you’d have the ultimate freedom. You are allowed to:
Every operation you do on the string would count for a unit cost. You’d have to keep that as low as possible.
For example,to convert “abccda” you would need at least two operations if we allowed you only to add characters. But when you have the option to replace any character you can do it with only one operation. We hope you’d be able to use this feature to your advantage.
InputThe input file contains several test cases. The first line of the input gives you the number of test cases, T (1≤T≤10). Then T test cases will follow,each in one line. The input for each test case consists of a string containing lower case letters only. You can safely assume that the length of this string will not exceed 1000 characters.
OutputFor each set of input print the test case number first. Then print the minimum number of characters needed to turn the given string into a palindrome.
Sample Input Output for Sample Input
题意：有3种操作，每种操作花费1单位花费。问最少的花费 区间DP：求最小花费。 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
typedef long long LL;
using namespace std;
#define REPF( i,a,b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i,n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a,x ) memset ( a,x,sizeof a )
const int INF=0x3f3f3f3f;
const int maxn=1100;
int dp[maxn][maxn];
char str[maxn];
int t;
int main()
{
int cas=1;
scanf("%d",&t);
getchar();
while(t--)
{
gets(str+1);
int len=strlen(str+1);
CLEAR(dp,INF);
for(int i=1;i<=len;i++)
{
if(str[i]==str[i+1])
dp[i][i+1]=0;
dp[i][i]=0;
}
for(int l=1;l<=len;l++)
{
for(int i=1;i+l<=len;i++)
{
int j=i+l;
if(str[i]==str[j])
dp[i][j]=min(dp[i][j],dp[i+1][j⑴]);
else
{
dp[i][j]=min(dp[i+1][j],dp[i][j⑴])+1;
dp[i][j]=min(dp[i][j],dp[i+1][j⑴]+1);
}
}
}
printf("Case %d: ",cas++);
printf("%d
",dp[1][len]);
}
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |