?

? ? ?非常好的一道思維性題目，想了很久才想出來qwq(我好笨啊)

? ? ?考慮a[]數組有什么用，首先可以yy出一些性質 (設num[i]為原來第i個位置的數是什么 , 因為題目說至少有一個排列可以滿足a[]，所以我們就假設num[]沒有相同的元素)：

? ? ? ? ?1. 當 a[i] == a[j] 且 i<j 的時候，我們可以得出 num[i] > num[j] ,因為如果反過來的話 a[j] 就至少是 a[i]+1 了。

? ? ? ? ?2. 對于任意一個 a[i] ，考慮所有 a[j] + 1 == a[i] 的 j，它們中至少有一個要滿足 : num[j] < num[i]；而很顯然，因為上一個性質的傳遞性，所以只需要找到最大的 j 然后讓num[j] < num[i] 就好了，也就是說每個 位置 至多 會和前面的一個位置 有必然的大小關系。

? ?

? ? ?然后我們把<當作邊，可以發現原圖變成了一個森林。而現在我們的任務就是：求出原序列的一個拓撲排序，使得反向lis和最大。

? ? ?這個好像還不是很容易啊，填一個數帶來的影響太多了。

? ? ?不過我們最初內心肯定都會有一個想法：貪心，盡量讓靠后的位置匹配小的數。

? ? ?

? ? ?但是我一開始心里有一個顧慮： 如果一個位置很靠后，但是因為它必須要小于一個很靠前的位置(或者說它的爸爸編號很小)，從而被耽誤導致答案很劣怎么辦？

? ? ?不過畫圖之后證明這種情況是不存在的！

? ? ?可以發現森林的第i層就是由 所有 a[x] == i 的 x 組成的，而每個節點會向上一層最大的 編號小于自己的點 連邊，所以這就保證了一種貪心的正確性：我們從虛根(0)開始，采取每次走編號最大的兒子的先序遍歷策略。

? ? ?這種貪心的正確性在于，我們在走一個點i之前經過的點，要么是i的祖先(欽定要比它小的)，要么編號比i大(編號靠后的小答案更優)。

?

? ? ?于是就做完了hhhhhhhh(雖然代碼被我壓得很短)

?

#include<bits/stdc++.h> #define ll long long #define pb push_back using namespace std; const int maxn=100005; vector<int> g[maxn]; int n,m,pre[maxn],A,num[maxn],now,f[maxn],M[maxn]; inline void update(int x,int y){ for(;x<=n;x+=x&-x) f[x]=max(f[x],y);} inline int query(int x){ int an=0; for(;x;x-=x&-x) an=max(an,f[x]); return an;} void dfs(int x){ if(x) num[x]=++now; for(int i=g[x].size()-1;i>=0;i--) dfs(g[x][i]);} int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&A),g[pre[A-1]].pb(i),pre[A]=i;dfs(0); ll ans=0;for(int i=n;i;i--) M[i]=query(num[i]-1)+1,update(num[i],M[i]),ans+=(ll)M[i];printf("%lld\n",ans);return 0; }

　　

轉載于:https://www.cnblogs.com/JYYHH/p/8963995.html

總結

以上是生活随笔為你收集整理的[TJOI2014] Alice and Bob的全部內容，希望文章能夠幫你解決所遇到的問題。

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