UVA - 531Compromise(LIS)
제목의 대의: 두 단락의 말을 제시하고 그 안에서 가장 긴 공공 단어의 서열을 찾아낸다.그리고 임의의 하위 서열을 출력합니다.
문제풀이: LIS.
코드:
#include <cstdio>
#include <cstring>
const int N = 105;
const int M = 35;
char w1[N][M];
char w2[N][M];
int f[N][N];
int p[N][N][2];
int ans[N];
int n1, n2;
void printf_ans (int x, int y) {
if (x == 0 || y == 0)
return;
printf_ans (p[x][y][0], p[x][y][1]);
if (strcmp (w1[x - 1], w2[y - 1]) == 0)
ans[f[x][y]] = x - 1;
}
int main () {
n1 = n2 = 0;
while (scanf ("%s", w1[n1++]) != EOF) {
while (scanf ("%s", w1[n1]) && w1[n1][0] != '#') {
n1++;
}
while (scanf ("%s", w2[n2]) && w2[n2][0] != '#') {
n2++;
}
for (int i = 0; i <= n1; i++)
f[i][0] = 0;
for (int i = 0; i <= n2; i++)
f[0][i] = 0;
for (int i = 1; i <= n1; i++)
for (int j = 1; j <= n2; j++) {
if (strcmp(w1[i - 1], w2[j - 1]) == 0) {
f[i][j] = f[i - 1][j - 1] + 1;
p[i][j][0] = i - 1;
p[i][j][1] = j - 1;
} else {
if (f[i][j - 1] > f[i - 1][j]) {
f[i][j] = f[i][j -1];
p[i][j][0] = i;
p[i][j][1] = j - 1;
} else {
f[i][j] = f[i - 1][j];
p[i][j][0] = i - 1;
p[i][j][1] = j;
}
}
}
printf_ans(n1, n2);
for (int i = 1; i < f[n1][n2]; i++)
printf ("%s ", w1[ans[i]]);
printf ("%s
", w1[ans[f[n1][n2]]]);
n1 = n2 = 0;
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
