程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 10739 String to Palindrome (dp)

uva 10739 String to Palindrome (dp)

編輯:C++入門知識

uva 10739 String to Palindrome (dp)


uva 10739 String to Palindrome

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:

Add any character at any position
Remove any character from any position
Replace any character at any position with another character

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.

Input
The 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.

Output

For 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

6

tanbirahmed

shahriarmanzoor

monirulhasan

syedmonowarhossain

sadrulhabibchowdhury

mohammadsajjadhossain

Case 1: 5

Case 2: 7

Case 3: 6

Case 4: 8

Case 5: 8

Case 6: 8

題目大意:給出一個字符串,有三種操作:增加,刪除,修改。問將該字符串修改為回文字符串,需要的最少操作數。

解題思路:dp[i][j]表示區間i到j要修改為回文字符串的最少操作數。 當s[i]==s[j]時,dp[i][j]=dp[i+1][j?1];當s[i]!=s[j]時,dp[i][j]=min(dp[i+1][j],dp[i][j?1],dp[i+1][j?1])+1

dp[i + 1][j]和dp[i][j + 1]代表增加和刪除,dp[i + 1][j - 1]代表修改。

#include 
#include 
#include 
#include 
#include 
#define N 1005
using namespace std;
typedef long long ll;
char s[N];
int dp[N][N];
int main() {
    int T, Case = 1;
    scanf("%d", &T);    
    while (T--) {
        scanf("%s", s);
        int len = strlen(s);
        memset(dp, 0, sizeof(dp));  
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i + 1; j < len; j++) {
                if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
                else {
                    dp[i][j] = min(min(dp[i + 1][j], dp[i][j - 1]), dp[i + 1][j - 1]) + 1;
                }
            }
        }
        printf("Case %d: %d\n", Case++, dp[0][len - 1]);
    }
    return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved