51nod_1006 최대 공통 하위 시퀀스, 출력 경로【DP】
A와 B의 가장 긴 공통 서열을 구하는 문자열 A B를 두 개 주십시오. (서열은 연속적이지 않습니다.)
예를 들어 두 개의 문자열은 다음과 같다.
abcicba
abdkscab
ab는 두 열의 서열이고 abc도 abca이며 그 중에서 abca는 이 두 문자열의 가장 긴 서열이다.
， ， 1 。아이디어:
DP, DP 로깅 경로.
코드:
string a,b;
int f[1005][1005];
int path[1005][1005];
void _print(int x,int y){
if(!x||!y) ret;
int t=path[x][y];
if(!t)
_print(x-1,y-1);
else if(t<0)
_print(x-1,y);
else
_print(x,y-1);
if(!t) print("%c",a[x-1]);
}
int main(){
cin>>a>>b;
int la=a.length(), lb=b.length();
mem(f,0);
mem(path,0);
rep(i,1,la) rep(j,1,lb){
f[i][j]=max( f[i-1][j],f[i][j-1] );
if(f[i-1][j]>f[i][j-1]){
f[i][j]=f[i-1][j];
path[i][j]=-1;
}
else{
f[i][j]=f[i][j-1];
path[i][j]=1;
}
if(a[i-1]==b[j-1]){
if(f[i-1][j-1]+1>f[i][j]){
f[i][j]=f[i-1][j-1]+1;
path[i][j]=0;
}
}
}
_print(la,lb); cout<<endl;
return 0;
}전재 대상:https://www.cnblogs.com/fish7/p/4409427.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
