Cyborg Genes-전자인의 유전자(UVA-10723)(Dp 두 개 안 썼어, 최우성 Dp 안 썼어! 새로운 사고방식! 구덩이 입력 But 간단)

앞말

제목

제목 대의

사고방식

DP 정의

상태 전이 방정식

초기화

응답 출력

코드

문외한

전언

틈이 나서 한참 동안 나를 함정에 빠뜨렸더니, 나로 하여금 이것저것 고치게 했다

제목.

두 개의 제목 전송문(UVA 약간 끊김) UVA vjudge

제목의 대의.

두 개의 A~Z로 구성된 문자열(길이가 30을 초과하지 않음)을 입력하고 가장 짧은 문자열을 찾아 두 문자열을 모두 하위 시퀀스로 입력합니다(연속적으로 나타나지 않음).너는 가장 짧은 열의 길이를 통계하는 것 외에, 가장 짧은 열의 개수를 통계해야 한다.샘플을 꼼꼼히 코를 해봅시다~ in i n.

3
ABAAXGF
AABXFGA
ABA
BXA
AABBA
BBABAA

out o u t

Case #1: 10 9
Case #2: 4 1
Case #3: 8 10

사고의 방향

DP 정의

크크, 이 문제는 내가 아주 잘 이해할 수 있는DP 정의를 사용했다. 마지막 두 가지 답안은 모두 잘 처리되었다. f[i][j][l]: a열 전 i개, b열 전 j개의 구성 길이가 l인 방안 수 f[i][j] [l]: a열 전 i개, b열 전 j개의 구성 길이가 l인 방안 수. 주의, 여기 l는 max(i, j)<=l<=i+j ax(i, j)

상태 이동 방정식

사실 쓰기도 좋다. ① a[i]==b[j]a[i]==b[j]일 경우 조합열에 해당하는 l위가 a[i]|b[j]일 경우 직접 f[i][j][l]=f[i-1][j-1][l-1][l-1][l-1]f[i][j]=f[i]=f[i-1][j-1][j-1][l-1][l-1][l-1]][l-1]]]][l-1]=a[i]=a[i]=a[i]b[j] a [ i ] ! = b[j]때 우리는 조합열 l l위를 a[i]a[i]로 할까 b[j]b[j]로 할까 I로 할까 고민해야 한다.a[i]a[i]를 넣고 이것은 작성법이므로 주의해야 한다. 따라서 f[i][j][l]+=f[i-31][j][l-31]f[i][j][l]+=f[i-31][j][l-31]l자리를 ii에게 남기고 II를 놓아라.b[j]b[j]를 넣고, f[i][j] [l][l]+=f[i] [j] [j] [j] [j] [j] [j] [j] [j] [j] [[j] [[j] [[i] [j 1] [j 1] [j 1] [j 1] [j] [i] [[j] [i] [i] [j] [j] [j] [j] [j] [j] [j] [j]++ + [[i] [j] [i] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] + f [i] [j -3 1] [l -3 1]

초기화

우리가 초기화할 때 f[0][0][0]f[0][0][0]를 1로 부여해야 할 뿐만 아니라 f[i][0][i](1<=i<=n)와 f[0][j](1<=j<=m)도 모두 1로 해야 한다. 그러면 Dp가 된다.

응답 출력

Dp의 정의를 살펴보자. f[i][j][l]: a열 전 i개, b열 전 j개 구성 길이가 l인 열의 방안 수 f[i] [j] [l]: a열 전 i개, b열 전 j개 구성 길이가 l인 방안 수. 그러면 우리가 답을 찾을 때 l를 맥스(n, m)에서 n+m ax(n, m)에서 n+m로 직접 매거하여 답을 찾자. f[n][m] [l]의 값만 있으면 [l]의 방안이 있다.여기 제목은 길이를 우선적으로 충족시켜야 하기 때문에 f[n][m][l]와 ll를 직접 출력하면 됩니다.

코드

#include
#include
#include
using namespace std;
int read(){
    int f=1,x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}  
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;
}
#define MAXN 30
#define INF 0x3f3f3f3f
char a[MAXN+5],b[MAXN+5];
int f[MAXN+5][MAXN+5][2*MAXN+5];
int main(){//a  i ,b  j       l    
    int T=read();
    for(int t=1;t<=T;t++){
        cin.getline(a+1,MAXN+5);cin.getline(b+1,MAXN+5);
        int n=strlen(a+1),m=strlen(b+1);
        f[0][0][0]=1;//   
        for(int i=0;i<=n;i++)
            f[i][0][i]=1;
        for(int j=0;j<=m;j++)
            f[0][j][j]=1;
        for(int i=1;i<=n;i++)//Dp
            for(int j=1;j<=m;j++)
                for(int l=max(i,j);l<=i+j;l++){
                    if(a[i]==b[j]) f[i][j][l]=f[i-1][j-1][l-1];
                    else f[i][j][l]=f[i-1][j][l-1]+f[i][j-1][l-1];
                }//Dp          
        for(int i=max(n,m);i<=n+m;++i)
            if(f[n][m][i]){//   
                printf("Case #%d: %d %lld
",t,i,f[n][m][i]);
                break;
            }//    ,    
        memset(f,0,sizeof(f));
    }
    return 0;
}

주제 밖의 말

다 만든 후에 인터넷에서 LIS와 관련된 것이 무엇인지, 어떤 답안은 용척원리로 출력해야 하는지 모두 너무 약하다~~

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

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

[BOJ]11048(python)

python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...

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

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

Cyborg Genes-전자인의 유전자(UVA-10723)(Dp 두 개 안 썼어, 최우성 Dp 안 썼어! 새로운 사고방식! 구덩이 입력 But 간단)

전언

제목.

제목의 대의.

사고의 방향

DP 정의

상태 이동 방정식

초기화

응답 출력

코드

주제 밖의 말

좋은 웹페이지 즐겨찾기