acwing 향상반 - 동적 기획 2

acwing 향상반 - 동적 기획 2
최장 상승 서열 문제
우호 도시

#include 
using namespace std;
const int N = 5010;
int dp[N];
typedef pair<int, int> PP;
PP a[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 0;i<n;i++)scanf("%d %d",&a[i].first,&a[i].second);
    sort(a,a+n);
    for(int i = 0;i<n;i++){
        dp[i] = 1;
        for(int j = 0;j<i;j++){
            if(a[i].second > a[j].second){
                dp[i] = max(dp[i],dp[j]+1);
            }
        }
    }
    int res = 1;
    for(int i = 0 ;i<n;i++)res = max(res,dp[i]);
    printf("%d
",res);
    return 0;
}

먼저 서열을 정하고 문제를 최장 상승 서열 문제로 전환한다.상태는 i로 끝나는 최i 상승 서열이나 i로 끝나는 최장 상승 서열과
미사일 방어 시스템

#include 
using namespace std;
const int N = 55;
int w[N];
int up[N],down[N];

int ans;
int n;

void dfs(int now,int nu,int nd){
    if(nu + nd >= ans)return;
    if(now == n){
        ans = nu + nd;
        return;
    }
    //   now         
    int k = 0;
    while (k<nu && up[k] > w[now])k++;
    int t = up[k];
    up[k] = w[now];
    if(k<nu)dfs(now+1,nu,nd);
    else{
        dfs(now+1,nu+1,nd);
    }
    up[k] = t;

    //  now         
    k = 0;
    while (k<nd && down[k] < w[now])k++;
    t = down[k];
    down[k] = w[now];
    if(k<nd)dfs(now+1,nu,nd);
    else{
        dfs(now+1,nu,nd+1);
    }
    down[k] = t;
}


int main()
{
    while (cin>>n,n){
        for(int i = 0;i<n;i++)cin>>w[i];
        ans = n;
        dfs(0,0,0);
        cout<<ans<<endl;
    }
    return 0;
}

사고방식은 LIS에 dfs를 더하는 것이다. dfs가 최소치를 구하는 방법은 전역적으로 최소화하거나 교체하여 깊이 있게 하는 것이다. 둘 다 가능하다.bfs를 사용하지 않는 것은 bfs가 일반적으로 상태가 폭발하여 메모리를 너무 많이 차지하고 가지치기가 쉽지 않기 때문이다.
최장 공통 상승 서브 시퀀스

#include 
using namespace std;
const int N = 3010;

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

    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            dp[i][j] = dp[i-1][j];
            if(a[i] == b[j]){
                dp[i][j] = max(dp[i][j],1);
                for(int k = 1;k<j;k++){
                    if(b[k] < b[j]){
                        dp[i][j] = max(dp[i][j],dp[i-1][k]+1);
                    }
                }
            }
        }
    }
    int res = 0;
    for(int i = 1;i<=n;i++)res = max(res,dp[n][i]);
    printf("%d
",res);
    return 0;
}

사고방식은 최장 상승 서열과 최장 공공 서열 서열을 결합시키는 것이다. dp[i][j]는 b[j]로 끝나는 것과 a[:i]의 최장 공공 상승 서열 길이의 최대치를 나타낸다.
최적화는 코드 차원에서 등가 변형을 하는 것이다

#include 
using namespace std;
const int N = 3010;

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

    for(int i = 1;i<=n;i++){
        int maxv = 1;
        for(int j = 1;j<=n;j++){
            dp[i][j] = dp[i-1][j];
            if(a[i] == b[j]) dp[i][j] = max(maxv,dp[i][j]);
            if(b[j] < a[i]) maxv = max(dp[i][j]+1,maxv);
        }
    }
    int res = 0;
    for(int i = 1;i<=n;i++)res = max(res,dp[n][i]);
    printf("%d
",res);
    return 0;
}

기록 1-j 중 만족 b[k]