배열 문자열 uva 10405 - Longest Common 하위 시퀀스 (최 장 공통 하위 시퀀스)

본 논문 에서 우 리 는 주로 배열 문자열 의 내용 을 소개 하고 자신 에 게 좋 은 제안 이 있다 고 생각 합 니 다.
    제목: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1346
    클래식 LCS 퀴즈...
    입문 하 는 것 이 좋다.내 첫 dp 문제 야.
    그러나 매우 구덩이 에 있 는 점 은 데이터 가 하나의 배열 이 있 는 것 같다 는 것 이다. 이것 은 while (gets (a) 로 이렇게 순환 하면 실 수 를 할 수 있다 는 것 을 의미한다. 두 개의 꼬치 로 함께 읽 어야 한 다 는 점 에서 나 는 몇 번 이나 구덩이 에 빠 졌 다.하지만 누 군가 읽 기 문자열 로 쓴 것 같 지만 실수 하지 않 았 다 이에. 내 가 잘못 판단 한 것 인지 다른 문제 인지 모르겠다.
    매일 같은 이치
옛사람 들 은 "해 나 백 천, 용 내 대" 라 고 말 했다. 인간 세상 에 갈등 과 싸움 이 없 을 수 는 없다. 우 리 는 공명정대 한 마음 과 너 그 러 운 미소 로 그것 을 대해 야 한다.하 버드 도 "용서 와 용 서 를 받 는 말로 설명 할 수 없 는 기쁨 은 신 도 부러워 할 만 한 큰 즐거움" 이 라 고 말 한 적 이 있다. 관용 에서 즐거움 을 누리 고 양해 에서 행복 을 느끼 자.
    또 하 나 는 dp 문 제 를 처음 풀 었 을 때 알고리즘 을 알 아 본 후에 문자열 을 어떻게 읽 어야 배열 의 첫 번 째 가 0 인지 몰 랐 다. 마지막 으로 다른 사람의 코드 를 참고 한 후에 gets (a + 1) 와 같은 형식 으로 문자열 을 읽 고 strlen (a + 1) 으로 문자열 의 길 이 를 가 져 오 는 것 이 밝 아 졌 다.
    나중에 저 는 정상적으로 읽 을 수 있다 는 것 을 알 게 되 었 습 니 다. dp 에서 저장 배열 을 처리 할 때 아래 표 시 를 모두 + 1 하면 됩 니 다.
    

#include<cstdio>

#include<cstring>

#define MAXN 1010



char a[MAXN], b[MAXN];

int c[MAXN][MAXN];



int max(int a, int b)

{

	if (a > b)

		return a;

	return b;

}



int main()

{

	while (gets(a + 1) && gets(b + 1))

	{

		int al = strlen (a + 1), bl = strlen (b + 1);

		memset(c, 0, sizeof(c));

		for (int i = 1; i <= al; i++)

			for (int j = 1; j <= bl; j++)

				if (a[i] == b[j])

					c[i][j] = c[i - 1][j - 1] + 1;

				else

					c[i][j] = max(c[i - 1][j], c[i][j - 1]);

		printf("%d
", c[al][bl]);

	}

	return 0;

}

글 이 끝나 면 프로그래머 의 농담 어록 을 공유 합 니 다. 시스템 프로그래머 1. 두피 가 자주 저 립 니 다. 파란색 화면 을 볼 때 뚜렷 하고 화면 에 아무것도 보이 지 않 을 때 특히 뚜렷 합 니 다.2. 엘리베이터 를 탈 때 항상 다운 이 걱정 되 고 벽 에서 reset 키 를 찾 습 니 다.3. 손톱 이 너무 길 어 요. F7 부터 F12 까지 누 르 면 힘 이 덜 들 어 요.4. 손 에 물건 이 있 으 면 계속 누 르 고 Alt - F, S 인 줄 알 았 다.5. 기계 상 자 는 하 드 디스크 가 돌아 가 는 지 여 부 를 판단 하기 위해 뚜껑 을 닫 지 않 습 니 다.6. 이상 하 게 다른 사람 을 미행 하고 손 에 F10 을 계속 누 릅 니 다.7. 모든 인터페이스 에 하 드 디스크 를 꽂 았 기 때문에 26 개의 자모 가 부족 하 다 고 생각 합 니 다.8. 틈 만 나 면 '다음 생 엔 프로그래머 안 해' 라 고 중얼거린다.9. 항상 9 번 이후 가 a 번 이 라 고 생각 합 니 다.10. 바 이러 스 는 두 렵 지 않 지만 자신의 절차 가 두 렵 습 니 다.