hdu 5125(LIS变形)

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=5125

题解:

这个题dp[i][0],dp[i][1]数组分别记录在第i个位置取a[i]和b[i]时可以取到最长上升子序列的长度,然后开一个m[i][0]和m[i][1]分别表示取到第i个位置时最少的交换次数.然后进行4次比较,最后取最大值的时候非常巧妙,如果m[i][0]>M,那么证明这个序列里面多了 m[i][0]-M 个数,所以要减掉这么多个数.

蒟蒻感觉别人好强啊....

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include <queue>

using namespace std;

const int N = ;

int a[N],b[N],dp[N][],m[N][];

int main()

{

    int tcase;

    scanf("%d",&tcase);

    while(tcase--){

        int n,M;

        scanf("%d%d",&n,&M);

        for(int i=;i<=n;i++){

            scanf("%d%d",&a[i],&b[i]);

        }

        memset(m,,sizeof(m));

        memset(dp,,sizeof(dp));

        dp[][] = dp[][]=m[][] =;

        for(int i=;i<=n;i++){

            dp[i][]=dp[i][] = m[i][] =;

            for(int j=;j<i;j++){

                if(a[i]>a[j]){

                    if(dp[i][]<dp[j][]+||dp[i][]==dp[j][]+&&m[i][]>m[j][]){

                        dp[i][] = dp[j][]+;

                        m[i][] = m[j][];

                    }

                }if(a[i]>b[j]){

                    if(dp[i][]<dp[j][]+||dp[i][]==dp[j][]+&&m[i][]>m[j][]){

                        dp[i][] = dp[j][]+;

                        m[i][] = m[j][];

                    }

                }if(b[i]>a[j]){

                    if(dp[i][]<dp[j][]+||dp[i][]==dp[j][]+&&m[i][]>m[j][]+){

                        dp[i][] = dp[j][]+;

                        m[i][] = m[j][]+;

                    }

                }if(b[i]>b[j]){

                    if(dp[i][]<dp[j][]+||dp[i][]==dp[j][]+&&m[i][]>m[j][]+){

                        dp[i][] = dp[j][]+;

                        m[i][] = m[j][]+;

                    }

                }

            }

        }

        int MAX = ;

        for(int i=;i<=n;i++){

            if(m[i][]<=M) MAX = max(dp[i][],MAX);

            else MAX = max(dp[i][]-m[i][]+M,MAX);

            if(m[i][]<=M) MAX = max(dp[i][],MAX);

            else MAX = max(dp[i][]-m[i][]+M,MAX);

        }

        printf("%d\n",MAX);

    }

    return ;

}

巴特西

hdu 5125(LIS变形)

最新文章

热门文章