hdu 6197 array array array(最長上昇サブシーケンス二分版)

タイトル:
長さnの配列をあげます.k個の要素を削除した後、配列を非増減シーケンスにすることができますか?
考え方:
1.記録dp[i]は、i番目の要素を末尾とする最長非増減サブシーケンスである.時間複雑度O(n*n);この問題データ範囲T;
コード:

#include 

using namespace std;
const int maxn = 1e5+7;

int dp1[maxn],dp2[maxn],arr[maxn];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i = 1;i<=n;i++)
            scanf("%d",arr+i);
        for(int i = 1;i<=n;i++)
            dp1[i] = 1,dp2[i] = 1;
        for(int i = 2;i<=n;i++)
        {
            for(int j = 1;j=arr[i])
                    dp2[i] = max(dp2[i],dp2[j]+1);
            }
        }
        int len = 1,len1 = 1;;
        for(int i = 1;i<=n;i++)
            len = max(len,dp1[i]),len1 = max(len1,dp2[i]);
        if(min(n-len,n-len1)<=k)
            printf("A is a magic array.
");
        else
            printf("A is not a magic array.
");
    }
    return 0;
}

2.dp[i]は、長さiの非増減シーケンスの末尾要素が取るべき最小(大)値として記載されている.したがって、n回のdp配列を更新するだけでよい.dp配列はインクリメント(減算)であるため、二分更新、時間複雑度O(nlogn)、AC
コード:

#include 

using namespace std;
const int maxn = 1e5+7;

int dp1[maxn],dp2[maxn],arr[maxn];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        int len = 1;
        for(int i = 1;i<=n;i++)
            scanf("%d",arr+i);
        dp1[len] = arr[1];
        for(int i = 2;i<=n;i++)
        {
            if(arr[i]>=dp1[len])
                dp1[++len] = arr[i];
            else
            {
                int l = 1,r = len;
                while(l>1;
                    if(dp1[mid]<=arr[i])
                        l = mid+1;
                    else
                        r = mid;
                }
                if(dp1[l]>arr[i])
                    dp1[l] = arr[i];
            }
        }
        int len1 = 1;
        dp2[len1] = arr[1];
        for(int i = 2;i<=n;i++)
        {
            if(arr[i]<=dp2[len])
                dp2[++len] = arr[i];
            else
            {
                int l = 1,r = len1;
                while(l>1;
                    if(arr[i]<=dp2[len])
                        l = mid+1;
                    else
                        r= mid;
                }
                if(arr[i]>dp2[l])
                    dp2[l] = arr[i];
            }
        }
        if(min(n-len,n-len1)<=k)
            printf("A is a magic array.
");
        else
            printf("A is not a magic array.
");
    }
    return 0;
}