题目描述

给一个长度为 \(n\) 的数组 \(a\) 。试将其划分为两个严格上升子序列，并使其长度差最小。

输入格式

输入包含多组数据。

数据的第一行为一个正整数 \(T\) ，表示数据组数。

每组数据包括两行:

第一行包括一个正整数 \(n\)

第二行包括一个长度为 \(n\) 的数组 \(a\)。

输出格式

对于每组数据输出一行一个整数，表示两个子序列的最小长度差。若不存在划分方案则输出\(-1\)

数据范围

\(T <= 10\)

简单: \(n <= 10^5, 0 <= a_i <= 2^{30}\), 最多只存在一种合法的划分方案

中等: \(n <= 10^3, 0 <= a_i <= 2^{30}\), 划分方案不超过\(10^{18}\)

困难: \(n <= 10^5, 0 <= a_i <= 2^{30}\), 划分方案不超过\(10^{18}\)

思路：直接上题解

如果一个位置\(k\)满足对于\(∀_i∈[1,k], ∀_j∈[k+1,n]， a_i < a_j\)恒成立，那么称\(k\)为一个分界点。找出所有分界点后可将序列分为若干段，每段之间相互独立，同时每段只存在不超过一种合法的方案数。求出每段的划分\(O(n)\)，再进行背包dp(\(O(nlogK)\)(\(K\)为可能的划分方案数))

其实就是说对于某个\(i\),满足\(max(1,i) < min(i + 1,n)\),则序列\([1,i]和[i+1,n]\)是相互独立的。

同理再来一个\(j > i\) 满足\(max(1,j) < min(j + 1,n)\), 则序列\([1,j]和[j+1,n]\)相互独立， 序列\([1,i]\)已经被划分出去，所以左边剩下\([i+1,j]\)。

简单证明这样的每段如果合法,只存在一种划分。

即证明对于合法的一段\([i,j](j > i + 1)\), 若不存在\(k\)，满足\(i<=k<j, max(i,k) < min(k+1,j)\),那么段\([i,j]\)只有一种划分方案。

反证不存在的情况有多种划分成立， 则存在的情况下只有一种划分，存在的情况下可以分成不可再分的几段，每段有多种划分，拼起来也会有多种划分， 与只有一种划分矛盾。

每段只有一种划分， \(m\)段组合起来的方案数为\(2^m = K\)， 所以\(m = logK\)

最后问题变成一个背包，从每段中选择一个序列长度组合起来，最后是否出现长度为\(j\)的序列(\(dp[j]\))

#include
    
     #define LL long long using namespace std;const int INF = 1e9;const int N = 1e5 + 10;int a[N];int mi[N], mx[N];int dp[2][N];int T, n, o;bool gao(int l, int r){    int first = 0, second = 0, cnt = 0;    for(int i = l;i <= r;i++){        if(first < a[i]) first = a[i], cnt++;        else if(second < a[i]) second = a[i];        else return false;    }    int d[2] = {cnt, r - l + 1 - cnt};    for(int i = 0;i <= n;i++) {        dp[o ^ 1][i] = 0;        for(int k = 0;k < 2;k++){            if(i >= d[k]) dp[o ^ 1][i] |= dp[o][i - d[k]];        }    }    o ^= 1;    return true;}int main(){    cin>>T;    while(T--){        cin>>n;        for(int i = 1;i <= n;i++) cin>>a[i];        if(n == 1){            cout<<-1<
     
      <= n;i++) mx[i] = max(mx[i - 1], a[i]);        for(int i = n;i >= 1;i--) mi[i] = min(mi[i + 1], a[i]);        memset(dp, 0, sizeof(dp));        dp[0][0] = 1;        int last = 1;        bool flag = true;        o = 0;        for(int i = 1;i <= n;i++){            if(mx[i] < mi[i + 1]){                if(!gao(last, i)){                    flag = false;                    break;                 }                last = i + 1;            }        }        int ans = -1;        if(flag){            for(int i = n / 2;i >= 0;i--) if(dp[o][i]){                ans = n - 2 * i;                break;            }        }        cout<
      
       <