hdu 1503 LCS
古典的なLCS問題.
少し時間をかけて完全に分かりました!
楽しい!DP!私はもうあなたを恐れません!
flag:冬休みにはすべてのタイプのテーマをそれぞれまとめます.できない人をはっきり教えて、自分でやっと本当の理解です.
MACコードは以下の通りである.
少し時間をかけて完全に分かりました!
楽しい!DP!私はもうあなたを恐れません!
flag:冬休みにはすべてのタイプのテーマをそれぞれまとめます.できない人をはっきり教えて、自分でやっと本当の理解です.
MACコードは以下の通りである.
#include
#include
using namespace std;
#define N 102
char a[N], b[N];
int dp[N][N],mark[N][N];
void LCS(int al, int bl){
int i, j;
for (i = 0; i <= al; i++){
dp[i][0] = 0;
mark[i][0] = 1;
}
for (i = 0; i <= bl; i++){
dp[0][i] = 0;
mark[0][i] = -1;
}
for (i = 1; i <= al; i++){
for (j = 1; j <= bl; j++){
if (a[i - 1] == b[j - 1]){
dp[i][j] = dp[i - 1][j - 1]+1;
mark[i][j] = 0;
}
else if (dp[i - 1][j] > dp[i][j - 1]){
dp[i][j] = dp[i - 1][j];
mark[i][j] = 1;
}
else{
dp[i][j] = dp[i][j - 1];
mark[i][j] = -1;
}
}
}
}
void printLCS(int i,int j){
if (i == 0 && j == 0){
return;
}
if (mark[i][j] == 0){
printLCS(i - 1, j - 1);
cout << a[i - 1];
}
else if (mark[i][j] == 1){
printLCS(i - 1, j);
cout << a[i - 1];
}
else if (mark[i][j] == -1){
printLCS(i, j - 1);
cout << b[j - 1];
}
}
int main(){
// freopen("TestDate.txt", "r", stdin);
int i,alength,blength;
while (cin >> a >> b){
for (i = 0; a[i] != '\0'; i++);
alength = i;
for (i = 0; b[i] != '\0'; i++);
blength = i;
LCS(alength, blength);
printLCS(alength, blength);
cout << endl;
}
return 0;
}