鏈接：https://www.lydsy.com/JudgeOnline/problem.php?id=1264

?

思路： n大小為20000*5，而一般的dp求最長公共子序列復(fù)雜度是 n*n的，所以我們必須優(yōu)化。

題目說了一個(gè)數(shù)會(huì)出現(xiàn)5次，那么我們可以預(yù)處理得到 第一個(gè)序列a[]每個(gè)數(shù)字分別在哪些位置，

因?yàn)榍驦CS的狀態(tài)轉(zhuǎn)移方程中當(dāng) s1[i-1] == s2[j-1]時(shí)，dp[i][j] = dp[i-1][j-1] + 1;只有當(dāng)兩個(gè)點(diǎn)相同時(shí)

值才會(huì)+1，我們可以對第二個(gè)序列b[]遍歷一遍，對于b[i]我們可以找到它在a[]上的5個(gè)位置，這5個(gè)

位置的dp[pos]都可以被更新,狀態(tài)轉(zhuǎn)移方程為： dp[pos] = max(p[1] - p[pos-1]) + 1, 對于dp[1] - dp[pos]，

這段區(qū)間的最大值，我們直接用樹狀數(shù)組維護(hù)就好了，時(shí)間復(fù)雜度為 O(n*logn)

?

實(shí)現(xiàn)代碼：

#include<bits/stdc++.h>
using namespace std;
#define ll long longconst int M = 2e5+10;
int a[M][7],c[M],dp[M],n;void update(int x,int p){while(x <= n*5){c[x] = max(c[x],p);x += (x&-x);}
}int getsum(int x){int ans = 0;while(x){ans = max(ans,c[x]);x -= (x&-x);}return ans;
}int main()
{int x;cin>>n;for(int i = 1;i <= n*5;i ++){cin>>x;a[x][++a[x][0]] = i;}for(int i = 1;i <= n*5;i ++){cin>>x;for(int j = 5;j >= 1;j --){int num = getsum(a[x][j]-1)+1;if(num > dp[a[x][j]]) dp[a[x][j]] = num,update(a[x][j],num);}}int ans = 0;for(int i = 1;i <= n*5;i ++){ans = max(dp[i],ans);}cout<<ans<<endl;return 0;
}

?

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

總結(jié)

以上是生活随笔為你收集整理的bzoj 1264: [AHOI2006]基因匹配Match (树状数组优化dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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