2013年4月5日

UVa 10739 - String to Palindrome


#include <stdio.h>
#include <string.h>

int dp[1005][1005];

int min(int a, int b) {
  return a < b ? a : b;
}

int main() {
  int T, C = 1;
  scanf("%d\n", &T);
  while (T--) {
    memset(dp, 0, sizeof(dp));
    char s[1005];
    gets(s + 1);
    int len = strlen(s + 1), l, r;
    for (l = len; l >= 1; l--)
      for (r = l; r <= len; r++)
        if (s[l] == s[r]) dp[l][r] = dp[l + 1][r - 1];
        else dp[l][r] = min(dp[l + 1][r - 1], min(dp[l + 1][r], dp[l][r - 1])) + 1;
    printf("Case %d: %d\n", C++, dp[1][len]);
  }
  return 0;
}

沒有留言:

張貼留言