선형 DP 요약(LIS, LCS, LCIS, 최장자 및)

한동안 선형 dp의 제목을 만들었을 때 선형 동적 계획을 정리하는 것은 하나의 수조에서 하는 것이 아니겠는가. 우선 가장 간단한 문제를 보자. 첫째, 가장 긴 필드와 다음은 상태 이동 방정식이다.

       for(int i=2;i<=n;i++)
        { if(dp[i-1]>=0) dp[i]=dp[i-1]+a[i]; else dp[i]=a[i]; }

예제 누드의 가장 긴 필드와 스크롤 수조를 사용할 수 있으며, 다음은 스크롤 수조로 쓴 것이다

#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <stdlib.h>

using namespace std;
int n;
int a;
int sum;
int _begin;
int _end;

int main()
{
    int t;
    scanf("%d",&t);
    int k=0;
    while(t--)
    {
        int max;
        int x=1;
        scanf("%d%d",&n,&a);
        sum=a;
        max=a;
        _begin=_end=1;
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&a);
            if(sum>=0)
            {
                sum+=a;
            }
            else
            {
                sum=a;
                x=i;
            }
            if(max<sum)
            {
                max=sum;
                _begin=x;
                _end=i;
            }

        }
          cout<<"Case "<<++k<<":"<<endl<<max<<" "<<_begin<<" "<<_end<<endl; 
        if(t)
            cout<<endl;


    }
    return 0;
}

업그레이드해 주세요. 2차원은요?즉 최대 서브 매트릭스와 상태 이동 방정식을 구하는 것이다. 사실은 1차원을 2차원으로 바꾸는 것이다. 어떻게 전환합니까?조작은 첫 번째 줄의 개수에 두 번째 줄의 대응하는 개수를 더해서 1차원으로 바꾸어 dp를 하고 세 번째 줄의 대응하는 개수를 더해서 DP를 하는 것이다.기점 줄은 각각 1에서 n까지 열거한다.

     for(int i=1;i<=n;i++)
       {
           memset(b,0,sizeof(b));
           memset(dp,0,sizeof(dp));
           for(int k=i;k<=n;k++)
           {
               for(int j=1;j<=n;j++)
               {
                   b[j]+=a[k][j];
                   if(dp[j-1]>=0)
                       dp[j]=dp[j-1]+b[j];
                   else
                       dp[j]=b[j];
                   if(sum<dp[j])
                       sum=dp[j];
               }
           }

       }

예제

#include <iostream>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>

using namespace std;
int a[105][105];
int n;
int dp[105];
int b[105];
int sum;
int main()
{
   while(scanf("%d",&n)!=EOF)
   {
       sum=0;
       for(int i=1;i<=n;i++)
       {
           for(int j=1;j<=n;j++)
           {
               scanf("%d",&a[i][j]);
           }
       }
       for(int i=1;i<=n;i++)
       {
           memset(b,0,sizeof(b));
           memset(dp,0,sizeof(dp));
           for(int k=i;k<=n;k++)
           {
               for(int j=1;j<=n;j++)
               {
                   b[j]+=a[k][j];
                   if(dp[j-1]>=0)
                       dp[j]=dp[j-1]+b[j];
                   else
                       dp[j]=b[j];
                   if(sum<dp[j])
                       sum=dp[j];
               }
           }

       }
       printf("%d
",sum);

   }
    return 0;
}

다음은 LIS 문제입니다. LIS는 최장 하강 서열이나 최장 상승 서열입니다.O(n^2)효율의 알고리즘도 있고 O(nlogn)효율의 알고리즘도 있다.먼저 O(n^2)효율의 알고리즘을 말하다.간단해, DP[j]=맥스(DP[i])+1 만족 조건 a[j]>a[i] 전태 전이 방정식

     for(int i=2;i<=n+1;i++)
        {
            int num=0;
            for(int j=i-1;j>=1;j--)
            {
                if(a[i]>a[j])
                    num=max(num,dp[j]);
            }
            dp[i]=num+1;
        }

O(nlogn)효율의 알고리즘은 이 블로그의 사실 과정을 참고하면 매우 간단하고 가장 긴 상승자 서열을 예로 들 수 있다.dp수조의 최종 길이는 가장 긴 상승자 서열이다. a[i]는 dp수조의 마지막 원소보다 크면 a[i]>dp[len]는 dp수조에 직접 가입한다.그렇지 않으면 첫 번째 a[i]보다 작은 dp[j]를 2점으로 찾은 다음에 dp[j]를 a[i]로 바꾸면 최종 dp수 그룹의 길이가 답이다.예제

#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>

using namespace std;
#define MAX 40000
int a[MAX+5];
int dp[MAX+5];
int n;
int search(int num,int l,int r)
{
    int mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(num>=dp[mid])
            l=mid+1;
        else
            r=mid-1;
    }
    return l;
}
int main()
{
    int cas=0;
    int x,y;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);

        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);

        }
        memset(dp,0,sizeof(dp));
        dp[1]=a[1];
        int len=1;
        for(int i=2;i<=n;i++)
        {
            if(a[i]>=dp[len])
                dp[++len]=a[i];
            else
            {
                int pos=search(a[i],1,len);
                dp[pos]=a[i];
            }
        }
        printf("%d
",len);
    }
    return 0;
}

가장 긴 연속 상승 서열을 구하거나 가장 긴 연속 하강 서열을 구하는 것도 비슷하다.이걸 풀려면 DP를 쓰지 말고 세그먼트 나무를 써야 해요.
다음은 LCS입니다. 가장 긴 공통 서열 문제입니다. 이것도 O(n^2)의 효율과 O(nlogn)의 효율 O(n^2)의 효율 보기 코드가 있습니다.

      for(int i=0;i<len1;i++)
        {
            for(int j=0;j<len2;j++)
            {
                if(s1[i]==s2[j])
                    dp[i+1][j+1]=dp[i][j]+1;
                else
                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);

            }
        }

O(nlogn) 효율은 LCS를 LIS 문제 a[] = {a, b, c,} b[] = {a, b, b, a, d}로 전환하는 것이다. 그러면 a의 a, b, c가 b에 나타난 위치는 각각 {0,4}, {1,3}, {2}이다.