題目鏈接：10453 - Make Palindrome

題目大意：給出一個(gè)字符串，通過(guò)插入字符使得原字符串變成一個(gè)回文串，要求插入的字符個(gè)數(shù)最小，并且輸出最后生成的回文串。

解題思路：和uva 10739的做法相似，只是本題只能插入字符，所以只要在考慮子問(wèn)題的同時(shí)記錄住最優(yōu)的選擇就可以了。

?

#include <stdio.h> #include <string.h> const int N = 1005;int n, dp[N][N], rec[N][N]; char str[N];int solve() {n = strlen(str);memset(dp, 0, sizeof(dp));memset(rec, 0, sizeof(rec));for (int i = n - 1; i >= 0; i--) {for (int j = i + 1; j < n; j++) {if (str[i] == str[j])dp[i][j] = dp[i + 1][j - 1];else {if (dp[i + 1][j] > dp[i][j - 1]) {dp[i][j] = dp[i][j - 1] + 1;rec[i][j] = 1;}else {dp[i][j] = dp[i + 1][j] + 1;rec[i][j] = -1;}}}}return dp[0][n - 1]; }void print(int a, int b) {if (a > b) return; // printf("%d!\n", rec[a][b]);if (a == b)printf("%c", str[a]);else if (rec[a][b] == 0) {printf("%c", str[a]);print(a + 1, b - 1);printf("%c", str[a]);}else if (rec[a][b] == 1) {printf("%c", str[b]);print(a, b - 1);printf("%c", str[b]);}else {printf("%c", str[a]);print(a + 1, b);printf("%c", str[a]);} }int main() {while (gets(str)) {printf("%d ", solve());print(0, n - 1);printf("\n");}return 0; }

?

?

總結(jié)

以上是生活随笔為你收集整理的uva 10453 - Make Palindrome(dp)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。