예비 지식

동적 기획의 기본 사상, LCS, LIS.

문제.

문자열 a, 문자열 b, a와 b의 LCIS (최장 공통 상승 서열) 를 구합니다.

사고의 방향

우선 우리는 이 문제가 상당히 많은 중첩자 문제를 가지고 있음을 알 수 있다.그래서 우리는 DP로 하려고 했다.DP의 최우선 과제는 무엇입니까?상태를 정의합니다.
1 정의 상태 F[i][j]는 a열의 처음 i자 b열의 첫 j자 및 b[j]로 구성된 LCIS의 길이를 나타냅니다.
왜 이게 다른 상태 정의가 아니에요?가장 중요한 이유는 이것밖에 할 줄 모른다는 것이다. 또 다른 이유는 이 정의가 제곱의 알고리즘을 만들 수 있다는 것을 알고 있기 때문이다.내가 이것밖에 할 줄 모르는 이유는 이 상태의 정의가 정말 쓰기 좋기 때문이다.그건 내가 나중에 얘기할게.
우리 이 상태를 고찰해 봅시다.이 상태가 어떤 상태로 옮길 수 있는지 생각하기는 까다로운 것 같다. 만약에 사고방식을 역전시켜 이 상태의 최우수치가 어떤 상태에 의존하는지 고찰하면 훨씬 쉽다.이 상태는 어떤 상태에 의존합니까?
우선, a[i]!=b[j]일 때는 F[i][j]=F[i-1][j]가 있다.왜 그랬을까?F[i][j]는 b[j]로 끝나는 LCIS이기 때문에 F[i][j]>0이면 a[1]...a[i]에는 반드시 하나의 문자가 있다. a[k]는 b[j]와 같다. (F[i][j]가 0과 같으면? 그 할당 여부는 아무런 영향이 없다).왜냐하면 a[k]!=a[i], 그러면 a[i]는 F[i][j]에 기여하지 않았기 때문에 우리는 그것을 고려하지 않고 F[i][j]의 최우수치를 얻을 수 있다.그래서 a[i]!=b[j]의 경우 반드시 F[i][j]=F[i-1][j]가 있다.이 점은 LCS 처리 방법을 참조합니다.
그럼 a[i]=b[j]는요?우선 최소한 길이가 1인 LCIS를 보장한 셈이다.그리고 우리는 가장 길고 b[j]가 그 끝에 이어질 수 있는 LCIS를 찾아야 한다.그 전에 제일 긴 LCIS가 어디 있었지?우선 우리가 찾아야 할 F수조의 1차는 i-1이다.i는 이미 b[j]와 짝을 지어 갔기 때문에 사용할 수 없다.그리고 i-2일 수도 없다. 왜냐하면 i-1이 i-2보다 더 우수하기 때문이다.2차원은요?그럼 매거b[1]...b[j-1]이야, 왜냐하면 너는 이 중에서 어느 것이 가장 길고 어느 것이 b[j]보다 작은지 모르니까.여기에 또 하나의 문제가 있는데, 어울리지 않을 리가 없겠는가?즉, a[i]=b[j]의 경우 F[i][j]=F[i-1][j]의 결정을 고려할 필요가 있습니까?답은 필요 없어.왜냐하면 b[j]가 a[i]와 짝짓지 않으면 이전의 a[1]와...a[j-1] 배합(F[i-1][j]>0, 0을 가정하면 a[i]와 배합이 우월하지 않을 것이다.(왜 필연적일까요? 왜냐하면 b[j]와 a[i]가 짝을 지은 후의 이동은max(F[i-1][k])+1이고, 이전의 i`와 짝을 지은 후는max(F[i'-1][k])+1이기 때문입니다.분명히 F[i][j]>F[i'][j], i'>i)가 있다
그래서 우리는 상태 이동 방정식을 얻어냈다.
a[i]!=b[j]:   F[i][j]=F[i-1][j]
a[i]==b[j]:   F[i][j]=max(F[i-1][k])+11<=k<=j-1&&b[j]>b[k]
이것은 시간의 복잡도가 O(n^3)인 DP로 제곱에서 아직 거리가 있다는 것을 보기 어렵지 않다.
그러나 이 알고리즘의 가장 관건적인 것은 합리적인 추이 순서에 따라 max(F[i-1][k])의 값을 우리가 이전에 F[i][k]에 방문했을 때 유지보수를 통해 max 변수를 업데이트할 수 있다는 것이다.어떻게 얻지?먼저 점차적으로 미루는 순서는 반드시 상태의 1차원은 외층에서 순환하고 2차원은 내층에서 순환해야 한다.즉 F[1][len(b)]를 계산한 다음에 F[2]를 계산한다[1].
만약 이 추이 순서에 따라 우리는 매번 외층 순환의 시작에 max 변수를 0으로 한 다음에 내층 순환을 시작할 수 있다.a[i]>b[j]일 때 max=F[i-1][j]를 명령합니다.a[i]=b[j]로 순환할 때 F[i][j]=max+1을 설정합니다.
마지막 답은 F[len(a)][1]...F[len(a)][len(b)]의 최대 값입니다.
참조 코드:

#include<cstdio>
#include<cstring>
intf[1005][1005],a[1005],b[1005],i,j,t,n1,n2,max;
intmain()
{
       scanf("%d",&t);
       while(t--)
       {
              scanf("%d%d",&n1,&n2);
              for(i=1;i<=n1;i++)scanf("%d",&a[i]);
              for(i=1;i<=n2;i++)scanf("%d",&b[i]);
              memset(f,0,sizeof(f));
              for(i=1;i<=n1;i++)
              {
                     max=0;
                     for(j=1;j<=n2;j++)
                     {
                            f[i][j]=f[i-1][j];
                            if(a[i]>b[j]&&max<f[i-1][j]) max=f[i-1][j];
                            if (a[i]==b[j])f[i][j]=max+1;
                     }
              }
              max=0;
              for(i=1;i<=n2;i++) if(max<f[n1][i]) max=f[n1][i];
              printf("%d
",max);
       }
}

사실 매우 시끄러운 1차원 알고리즘이 하나 더 있다.이 기초 위에서 1차원 공간을 눌러 버렸다.i가 x로 순환할 때 F[i]는 원래 F[x][j]를 나타낸다.만약 a[i]!=b[j], F[x][j]=F[x-1][j]값이 변하지 않기 때문에 F[x]값은 바꿀 필요가 없고 과거의 것을 그대로 사용하면 된다. 이것과 비교하여 유지보수하고 업데이트한 max값은 여전히 우리가 원하는 것이다.a[i]=b[j]일 때 F[x]의 값을 바꾸면 된다.구체적인 결합 코드 이해.
참조 코드:

#include<cstdio>
#include<cstring>
intf[1005],a[1005],b[1005],i,j,t,n1,n2,max;
intmain()
{
       scanf("%d",&t);
       while(t--)
       {
              scanf("%d%d",&n1,&n2);
              for(i=1;i<=n1;i++)scanf("%d",&a[i]);
              for(i=1;i<=n2;i++)scanf("%d",&b[i]);
              memset(f,0,sizeof(f));
              for(i=1;i<=n1;i++)
              {
                     max=0;
                     for(j=1;j<=n2;j++)
                     {
                            if (a[i]>b[j]&&max<f[j])max=f[j];
                            if (a[i]==b[j])f[j]=max+1;
                     }
              }
              max=0;
              for(i=1;i<=n2;i++) if(max<f[i]) max=f[i];
              printf("%d
",max);
       }
}