题目传送：Palindrome
思路：一看题目思路很清晰，就是求出字符串s和倒转s后的字符串t的最长公共子序列，但是一看空间开销有点大，如果开int就会爆，5000*5000有100MB了，这里可以开shortint，差不多正好可以过去，还有一种做法就是弄一个滚动数组，因为求LCS，根据状态转移方程可以知道，，只需要前一行和当前行就行了，所以开个2*5005就OK了，具体看代码
AC代码①：
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <queue>#include <stack>#include <vector>#include <map>#include <set>#include <deque>#include <cctype>#define LL long long#define INF 0x7fffffffusing namespace std;char s[5005];char t[5005];short int dp[5005][5005];int main() {int N;cin >> N;scanf("%s", s + 1);for(int i = 1; i <= N; i ++) {t[N – i + 1] = s[i];}t[N + 1] = '\0';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;}else {dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}}cout << N – dp[N][N] << endl;return 0;}
AC代码②：
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <queue>#include <stack>#include <vector>#include <map>#include <set>#include <deque>#include <cctype>#define LL long long#define INF 0x7fffffffusing namespace std;int dp[2][5005];char s[5005];char t[5005];int main() {int N;cin >> N;scanf("%s", s + 1);for(int i = 1; i <= N; i ++) {t[N + 1 – i] = s[i];}t[N + 1] = '\0';for(int i = 1; i <= N; i ++) {for(int j = 1; j <= N; j ++) {if(s[i] == t[j]) {dp[i % 2][j] = dp[(i – 1) % 2][j – 1] + 1;}else {dp[i % 2][j] = max(dp[(i – 1) % 2][j], dp[i % 2][j – 1]);}}}cout << N – dp[N % 2][N] << endl;return 0;}
好想从现在开始抱着你，紧紧地抱着你，一直走到上帝面前。
