程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ - 1159 - Palindrome （LCS + 優化）

POJ - 1159 - Palindrome （LCS + 優化）

編輯：C++入門知識

POJ - 1159 - Palindrome （LCS + 優化）

思路：一看題目思路很清晰，就是求出字符串s和倒轉s後的字符串t的最長公共子序列，但是一看空間開銷有點大，如果開int就會爆，5000*5000有100MB了，這裡可以開short int，差不多正好可以過去，還有一種做法就是弄一個滾動數組，因為求LCS，根據狀態轉移方程可以知道，只需要前一行和當前行就行了，所以開個2*5005就OK了，具體看代碼

AC代碼①：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#define LL long long
#define INF 0x7fffffff
using 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] = '';
	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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#define LL long long
#define INF 0x7fffffff
using 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] = '';
	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;
}

C++入門知識

STL中list的erase()方法，stllisterase方法

STL中list的erase()方法，stllisteras

哲學家就餐問題——MFC演示程序

[cpp] </pre><pre n

LeetCode 96:Unique Binary Search Trees

LeetCode 96:Unique Binary Sear

給出洗牌的一個算法，並將洗好的牌存儲在一個整形數組裡。

給出洗牌的一個算法，並將洗好的牌存儲在一個整形數組裡。

最簡單的銀行系統（1）

[cpp] /*

深入理解Aireplay-ng各種攻擊及其原理

[cpp] //------