P1439 【模板】最長公共子序列
許久沒有刷題，認為一個小學生教練到了普及一等的水平就可以安穩的睡了。孩子們外出上學的夢想湮滅。想傳出去的球又回來了，孩子水平高了很多，我安心的看著他們進步。弊端逐漸顯露，沒有人帶領，他們總是陷入各種迷茫。這種帶領不一定是知識上的，也許就是精神上的，那么我也重新打開兩年前的刷題暫停鍵，陪伴他們一起前行。
這道題非常神奇。對于一個有著簡單背包、線性動態規劃基礎的中年人來說非常的虐。
首先，我是這樣寫的。
#include<iostream> #include<cstdio> using namespace std; int a[100000],b[100000]; int f[10000][10000]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n;i++) { scanf("%d",&b[i]); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(a[i]==b[j]) { f[i][j]=max(f[i][j],f[i-1][j-1]+1); } else { f[i][j]=max(f[i-1][j],f[i][j-1]); } } cout<<f[n][n]; return 0; }
規規整整的最長公共子序列動態規劃（也苦苦啃了半天）
提交 50分
這才關注數據范圍，10^5 ，n^2一定崩。
于是發奮看題解，了解到離散的方式來處理。
于是有了這樣的變形，感覺比n^2高效了一些。能看懂這個離散，把公共子序列變為LIS 最長不下降子序列，是看了阮行止大佬的一篇題解
大佬一語點破夢中人，為了讓自己更清晰，我直接把第二個b數組弄成了一個相對于 a位置信息的數組，這樣只要求b的lis問題就可以了。
#include<iostream> #include<cstdio> using namespace std; int a[100000],b[100000],map[100000],t,f[100000],ans; int main() { int n; cin>>n; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); map[a[i]]=i; } for(int i=1;i<=n;i++) { scanf("%d",&t); b[i]=map[t]; } for(int i=1;i<=n;i++) { f[i]=1; for(int j=1;j<=i-1;j++) if(b[i]>b[j]) { f[i]=max(f[i],f[j]+1); } } for(int i=1;i<=n;i++) { ans=max(f[i],ans); } cout<<ans; }
結果還是50分。雖然提高了效率，但是還是n^2
導彈攔截只得了一半分的鍋又出來了，當時懶得去理解nlogn的算法，總要還。開始看這方面資料LIS nlogn算法
大佬諄諄教誨的 傳送門
有認識一個新的盲區，關于lowerbound和upperbound，再一次百度 另外一個大佬諄諄教誨的 傳送門
看懂了，AC。未來順便補上導彈攔截的空缺。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int a[100000],b[100000],map[100000],t,f[100000],ans,temp[100000]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); map[a[i]]=i; } for(int i=1;i<=n;i++) { scanf("%d",&t); b[i]=map[t]; } int len=0; for(int i=1;i<=n;i++) { if(b[i]>temp[len]) { temp[++len]=b[i]; continue; } t=upper_bound(temp,temp+len+1,b[i])-temp; temp[t]=b[i]; } cout<<len<<endl; }
浙公網安備 33010602011771號