正題

---

題目大意

長度為$n$的序列，分割成兩個上升子序列要求長度差最小

---

解題思路

我們對于$i<j,a_i\ge a_j$的點之間連邊，然后可以對于一個聯通塊進行二分圖染色，我們可以發現，如果我們先固定一個點的顏色，那么這個聯通塊的二分圖染色方案數為1或0。

之后兩個聯通塊互不影響，所以我們可以用$dp$來計算方案。

考慮繼續優化，我們可以發現如果$i$到$j$之間有連邊，那么對于任意一個$i<k<j$，$i$和$k$和$j$必定聯通，那么我們可以推得一個聯通塊必定是一個區間，而一個區間的分界點滿足該點前面的所有數都比后面的所有數要小。

因為劃分方案數為$2^{cnt}$(cnt為聯通塊數量。所以聯通塊數量不超過$log(1e18)$，可以通過本題

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<stack> using namespace std; const int N=1e5+10,K=300; int T,n,a[N],maxs[N],mins[N]; int cnt,b[K],e[K],z[K]; bool f[2][N]; stack<int> q1,q2; int main() {//freopen("sample2.in","r",stdin);scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);maxs[i]=max(maxs[i-1],a[i]);}mins[n+1]=2147483647/3;cnt=0;for(int i=n;i>=1;i--)mins[i]=min(mins[i+1],a[i]);for(int i=1;i<=n;i++)if(maxs[i]<=mins[i+1]||i==n)b[++cnt]=e[cnt-1]+1,e[cnt]=i;bool flag=0;for(int i=1;i<=cnt;i++){while(!q1.empty())q1.pop();while(!q2.empty())q2.pop(); for(int j=b[i];j<=e[i];j++){if(q1.empty()||a[j]>q1.top())q1.push(a[j]);else if(q2.empty()||a[j]>q2.top())q2.push(a[j]);else{flag=1;break;}}if(flag)break;z[i]=q1.size()-q2.size();}if(flag){printf("-1\n");continue;}memset(f,0,sizeof(f));f[0][0]=1;for(int i=1;i<=cnt;i++)for(int j=0;j<=n;j++)f[i&1][j]=f[~i&1][abs(j-z[i])]|f[~i&1][abs(j+z[i])];for(int j=0;j<=n;j++)if(f[cnt&1][j]){printf("%d\n",j);break;}} }

總結

以上是生活随笔為你收集整理的nssl1488-上升子序列【贪心,dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。