LightOJ 1033 - Generating Palindromes（dp）

本文主要是介绍LightOJ 1033 - Generating Palindromes（dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：LightOJ 1033 - Generating Palindromes

代码

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn = 105;int N, dp[maxn][maxn];
char s[maxn], t[maxn];int solve () {memset(dp, 0, sizeof(dp));for (int i = 1; i <= N; i++) {for (int j = 1; j <= N; j++)if (s[i] == t[j])dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = max(dp[i-1][j], dp[i][j-1]);}return dp[N][N];
}int main () {int cas;scanf("%d", &cas);for (int kcas = 1; kcas <= cas; kcas++) {scanf("%s", s + 1);N = strlen(s + 1);for (int i = 1; i <= N; i++)t[i] = s[N-i+1];printf("Case %d: %d\n", kcas, N - solve());}return 0;
}

这篇关于LightOJ 1033 - Generating Palindromes（dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---