Codeforces Beta Round #46 (Div. 2) E. Common ancestor

제목의 뜻
정의 변환:ai->bici: 문자열의ai 문자를bici 문자로 바꾸는 것을 의미합니다.두 문자열 s1s2를 다시 정의한 공공 조상 s3:s1s2는 s3에서 일부 변환을 거쳐 각각 얻을 수 있다.이제 길이가 50을 넘지 않는 두 개의 문자열을 드리겠습니다. 그들의 공공 조상 중 길이가 가장 짧은 것이 얼마인지 물어보세요. 이 길이를 출력하세요.
방법 분석
동적 기획, 만약에 우리가 모든 문자열에서 i번째 위치에서 j번째 위치까지 특정한 문자ch가 될 수 있는지 알게 된다면 우리는 첫 번째 문자열의 전 i1개와 두 번째 문자열의 전 i2에 따라 가장 짧은 공공 조상을 찾아 단계를 구분할 수 있다. 분명히 이렇게 구분된 단계는 최우수자 구조와 무후효성을 만족시킬 수 있다.정의된 상태는 첫 번째 문자열의 첫 번째 a 문자와 두 번째 문자열의 첫 번째 b 문자의 가장 짧은 공공 조상 길이이다. 그래서 다음과 같은 상태 이동 방정식을 쓸 수 있다.
f[a][b]=max{f[i][j]+1, f[a][b]} 그 중에서 i
이제 각 문자열의 [L, R] 구간 내의 하위 문자열이 압축을 거쳐 특정한 문자ch를 얻을 수 있는지 판단하는 방법이 됩니다.
이것도 동적 기획으로 할 수 있어요.
우리는 구간의 길이로 단계를 구분한다(기점과 종점의 길이로 단계를 구분할 수 없다). 정의된 상태는 g[i, i+L-1][ch]로 [i, i+L-1]이ch로 축소될 수 있는지를 나타낸다.상태 전환 방정식은 다음과 같이 전송 클로즈업과 비슷합니다.
g[i, L+i-1][ch] = g[i, L+i-1] [ch]||(g[i, k][b] & & g[k+1, i+L-1] [c] & &ch->bc), 그 중에서ch->bc는 bc가ch->bc로 축소될 수 있음을 나타낸다
이렇게 해서 이 문제는 해결되었다.
오후 내내 해 봤지만 DP 는 너무 적게 해 서 단계 를 나누는 경험 이 없기 때문에 많은 연습 을 해야 한다
AC 채널
Codeforces Beta Round #46 (Div. 2) E. Common ancestor
참조 코드

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int INT_INF=0x3fffffff;

bool compress[2][60][60][30];
char s[2][60], substitution[60][10];
int f[60][60], n, len[2];

void init(int id)
{
	len[id]=(int)strlen(s[id]);
	for(int i=0; i

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

UVA 1025_A Spy in the Metro

[제의] (소자서) 한 사람이 플랫폼 1에서 출발하면 차를 타려면 시간 T에 플랫폼 n에 도착해야 한다. 플랫폼에서 차를 기다리는 시간이 가장 짧기 때문에 그녀는 두 방향의 열차를 타고 버스가 정차할 때 갈아타야 한...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Codeforces Beta Round #46 (Div. 2) E. Common ancestor

좋은 웹페이지 즐겨찾기