LCIS vijos—P1264

오늘 dp에 대한 대표적인 예제가 LCIS에 관한 거예요.
먼저 문제집을 보겠습니다.
달을 숭배하는 고급 스파이로서 너의 임무는 항상 너를 죽도록 핍박한다.예를 들어 이번에 배월교주가 조령아 일행을 미행하고 시련굴 밑으로 잠입하라고 했다.시련굴 밑에는 오행법술의 최고 법술인 풍신, 뇌신, 설요, 화신, 산신의 주문이 숨어 있다고 한다.이런 법술을 배우기 위해서는 고된 노력을 기울여야 하지만 보답도 많다.바이월은 주문의 길이가 얼마인지 알려주길 바란다."당신: 주문의 구체적인 내용을 알고 싶으세요?"달맞이: "하지만 vijos는 special judge를 지원하지 않습니다."- -원래 큰 인물도 큰 인물의 슬픔이 있구나...)그래서 너는 몰래 한쪽에 숨어서 주문이 도대체 무엇인지 보고 싶었다.갑자기 하늘(?? 시련굴 밑에 하늘이 보인다??)아주 긴 숫자열 두 개가 나와서 미쳤어.과연 어떤 게 진짜 주문일까요?너는 이 두 가지 모두 주문이 아니라 진정한 주문은 그들과 밀접한 관계를 가진다는 것을 갑자기 생각했다.그러자 달맞이 메모를 펼쳤다. "The Real Incantation is Their Common Increasing Subsequence of Maximal Possible Length""망할 달맞이, E문까지 하다니!"너는 욕을 했지만, 한 집안의 막내의 생명을 위해 주문의 길이를 목숨을 바쳐 계산해야만 했다.
첫 번째 비헤이비어는 테스트 데이터가 있는 N을 나타내는 숫자입니다.각 그룹의 테스트 데이터에 대해 두 개의 숫자열을 묘사했다. 첫 번째 숫자는 위조 주문의 길이 M이고, 다음 M 개수는 위조 주문의 내용을 묘사했다.총 N행으로 줄마다 숫자가 하나씩 주어의 길이를 묘사했다.
문제는 착해요. 뭘 원하는지 바로 알려드릴게요.
최장 상승 공용 서열
LIS LCS를 어떻게 할 것인가에 대해 논의를 해 봤습니다.
지금 문제는 어떻게 얘네를 잘 합치느냐. 처음에 CRH랑 저랑 LCS를 직접 구해서 LIS를 찾으려고 했어요.
하지만 쉽게 반례를 찾았지만 슬기로운 우리가 어떻게 이렇게 곤란해질 수 있겠는가?사실 찾을 때 올라가는지 안 올라가는지 보면 돼요. 계속 올라가면 합법적인 길이예요. 마지막 패스 길이...그래 이제 끝이야!!!!!다음에 코드를 여러분께 못생긴 거 이해해 드릴게요. 때리지 마세요...

#include <stdio.h>
#include <algorithm>
using namespace std;
int dp[501][501];//    i     j             
int a[501];
int b[501];
int main()
{
    int x;
    scanf("%d",&x);
    for(int ii=1;ii<=x;ii++)
    {
        int ans=0;
        int l1;
        scanf("%d",&l1);
        for(int i=1;i<=l1;i++)
            scanf("%d",&a[i]);
        int l2;
        scanf("%d",&l2);
        for(int i=1;i<=l2;i++)
            scanf("%d",&b[i]);
        for(int i=1;i<=l1;i++)
        {
            int Max=0;
            for(int j=1;j<=l2;j++)
            {
                dp[i][j]=dp[i-1][j];
                if(a[i]>b[j])
                    Max=max(Max,dp[i-1][j]);
                else if(a[i]==b[j])
                    dp[i][j]=Max+1;
            }
        }   
        for(int j=1;j<=l2;j++)
            ans=max(ans,dp[l1][j]);
        printf("%d
",ans);
    }
}