題目描述

題目背景
在你的幫助之下，三仙獸終于弄清楚了到北京的道路，于是他們收拾一下行裝，出發(fā)了。

第一站他們要經(jīng)過(guò)被成為“米不亞亞亞亞爾”的神秘森林，由于有蓬絮這位走迷宮的高手打頭陣，前進(jìn)的道路變平坦了很多。但當(dāng)他們來(lái)到這片森林的核心地帶時(shí)，還是遇到了一點(diǎn)點(diǎn)小麻煩……

題目敘述
現(xiàn)在他們位于神秘森林的核心部位，面前有兩條主要的大道，不用說(shuō)，一條通向光明，一條通向黑暗。大家當(dāng)然想奔向光明，遠(yuǎn)離黑暗，可是蓬絮研究了半個(gè)時(shí)辰也研究不出個(gè)所以然。

倒是細(xì)心的花楹發(fā)現(xiàn)了線索，她在地上搜尋時(shí)，發(fā)現(xiàn)了遺落在草叢里的一張紙，紙上如是寫道：

致想要尋找出口的人們：
　　這里必須你們真正了解大地的運(yùn)行規(guī)律，才能破解難關(guān)。
　　現(xiàn)在，你們只需要拿這這張紙，大喊一聲：“哇呱呱呱呱呱呱呱呱呱呱~”，你們前方的地面上就會(huì)出現(xiàn)很多的木偶士兵，他們外貌各異。你們必須把他們排布成東邊一棵松樹上刻紋中寫出的陣列，正確的出口才會(huì)顯露出來(lái)。
　　正確的答案就在你們面前，只看你們能不能把握咯。

　　　　　　——米不亞亞亞亞爾之主：巴羅羅羅羅列吉

沒(méi)辦法，雖然這張破破爛爛發(fā)著臭氣的紙看上去不像真的，死馬當(dāng)作活馬醫(yī)，三人還是照做了。沒(méi)想到咒語(yǔ)剛說(shuō)完，前方“嗡～”的一聲起了巨大的煙霧。等到煙消云散，三獸定睛一看，地上果然出現(xiàn)了數(shù)不清的人偶。

他們開始相信這一張紙的真實(shí)性了，動(dòng)作快的勇氣趕忙找到附近的一棵松樹。果然，上面也刻著數(shù)不請(qǐng)的人偶圖案。

現(xiàn)在的任務(wù)就是如何調(diào)整木偶的順序了。整個(gè)木偶群可以看成一列排布的，所有的 n 個(gè)木偶不盡相同，編號(hào)為 1-n。由于仙獸功力有限，每次施法只能把一個(gè)木偶移動(dòng)到另兩個(gè)木偶之間（可以移到隊(duì)頭和隊(duì)尾）。

經(jīng)過(guò)三個(gè)時(shí)辰的仔細(xì)研究，勇氣已經(jīng)把所有的木偶都正確編號(hào)完畢（勇氣：累死俺也～她們兩個(gè)都不干事的……）。現(xiàn)在他需要你告訴他，要完成調(diào)整最少需要移動(dòng)多少次木偶，這樣來(lái)給他個(gè)心里準(zhǔn)備……

數(shù)據(jù)范圍
對(duì)于 60% 的數(shù)據(jù)，n <= 1000
對(duì)于 100% 的數(shù)據(jù)，n <= 100000

輸入格式

三行，第一行一個(gè)整數(shù) n，表示有 n 個(gè)木偶。
第二行，n 個(gè)整數(shù)（1-n），表示初始時(shí)木偶的排布。
第三行，n 個(gè)整數(shù)（1-n），表示目標(biāo)木偶的排布。

輸出格式

一行，一個(gè)整數(shù)，表示最少移動(dòng)次數(shù)。

?

?

題解：————————————————————————————————————————

贊！這道題實(shí)在是太贊了！！！

很顯然，每一個(gè)人偶最多只需要移動(dòng)一次便可到達(dá)正確位置。但是從樣例中可以看出，有一些人偶是不需要?jiǎng)拥?#xff0c;那么最終的答案便是?n?減去不需要移動(dòng)的人偶數(shù)。

這道題集LIS(最長(zhǎng)不下降序列)與LCS(最長(zhǎng)公共序列)于一身。也可以說(shuō)吸收了LCS的思想，或者是LCS的變形應(yīng)用。而且該題的數(shù)據(jù)范圍n<=100000使得LIS動(dòng)態(tài)規(guī)劃O(n*n)的算法超時(shí)，所以這里用需要用到LIS(nlgn)的算法，這在前面我的博客上都有介紹的。

數(shù)組a[i]記錄的是初始時(shí)木偶的排布，令c[a[i]]=i,所以c[]是遞增的。b[i]記錄的是移動(dòng)后木偶的排布。求c[b[i]]數(shù)列的最長(zhǎng)不下降序列長(zhǎng)度。

#include<iostream>
#include<cstring>
using namespace std;

int a[100001],b[100001],c[100001],f[100001],n,len=1;

int find(int x,int r){
??? int mid,l=1;
??? while(l<=r)
??? {
???? mid=(l+r)/2;
???? if(f[mid]==x) return mid;
???? if(f[mid]<x) l=mid+1;
???? if(f[mid]>x) r=mid-1;?????
?????????????? }
??? return l;
??? }

int main()
{
??? int i,j;
??? scanf("%d",&n);
???
??? for(i=1;i<=n;i++)
??? {scanf("%d",&a[i]);c[a[i]]=i;}
???
??? for(i=1;i<=n;i++)
??? scanf("%d",&b[i]);

??? memset(f,0,sizeof(f));
??? f[1]=c[b[1]];
??? for(i=2;i<=n;i++)
??? {
??? j=find(c[b[i]],len);
??? if(j>len) len=j;
??? f[j]=c[b[i]];
??? }
???
??? cout<<n-len<<endl;
??? system("pause");
??? return 0;
???
??? }

轉(zhuǎn)載于:https://www.cnblogs.com/noip/archive/2012/01/16/2324141.html

總結(jié)

以上是生活随笔為你收集整理的题目:大地的秘密的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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