?

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

? ? ?考慮a[]數(shù)組有什么用，首先可以yy出一些性質(zhì) (設(shè)num[i]為原來(lái)第i個(gè)位置的數(shù)是什么 , 因?yàn)轭}目說(shuō)至少有一個(gè)排列可以滿(mǎn)足a[]，所以我們就假設(shè)num[]沒(méi)有相同的元素)：

? ? ? ? ?1. 當(dāng) a[i] == a[j] 且 i<j 的時(shí)候，我們可以得出 num[i] > num[j] ,因?yàn)槿绻催^(guò)來(lái)的話 a[j] 就至少是 a[i]+1 了。

? ? ? ? ?2. 對(duì)于任意一個(gè) a[i] ，考慮所有 a[j] + 1 == a[i] 的 j，它們中至少有一個(gè)要滿(mǎn)足 : num[j] < num[i]；而很顯然，因?yàn)樯弦粋€(gè)性質(zhì)的傳遞性，所以只需要找到最大的 j 然后讓num[j] < num[i] 就好了，也就是說(shuō)每個(gè) 位置 至多 會(huì)和前面的一個(gè)位置 有必然的大小關(guān)系。

? ?

? ? ?然后我們把<當(dāng)作邊，可以發(fā)現(xiàn)原圖變成了一個(gè)森林。而現(xiàn)在我們的任務(wù)就是：求出原序列的一個(gè)拓?fù)渑判?#xff0c;使得反向lis和最大。

? ? ?這個(gè)好像還不是很容易啊，填一個(gè)數(shù)帶來(lái)的影響太多了。

? ? ?不過(guò)我們最初內(nèi)心肯定都會(huì)有一個(gè)想法：貪心，盡量讓靠后的位置匹配小的數(shù)。

? ? ?

? ? ?但是我一開(kāi)始心里有一個(gè)顧慮： 如果一個(gè)位置很靠后，但是因?yàn)樗仨氁∮谝粋€(gè)很靠前的位置(或者說(shuō)它的爸爸編號(hào)很小)，從而被耽誤導(dǎo)致答案很劣怎么辦？

? ? ?不過(guò)畫(huà)圖之后證明這種情況是不存在的！

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

? ? ?這種貪心的正確性在于，我們?cè)谧咭粋€(gè)點(diǎn)i之前經(jīng)過(guò)的點(diǎn)，要么是i的祖先(欽定要比它小的)，要么編號(hào)比i大(編號(hào)靠后的小答案更優(yōu))。

?

? ? ?于是就做完了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; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/JYYHH/p/8963995.html

總結(jié)

以上是生活随笔為你收集整理的[TJOI2014] Alice and Bob的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。