參考文章
子序列
一個序列 A = a 1 , a 2 , … , a n A=a_1,a_2,…,a_n A=a1?,a2?,…,an? 中任意刪除若干項,剩余的序列叫做 A 的一個子序列。也可以認為是從序列 A 按原順序保留任意若干項得到的序列。(例如:對序列{1,3,5,4,2,6,8,7}來說,序列{3,4,8,7}是它的一個子序列。)
LIS 最長上升子序列
代碼
轉移方程: d p [ i ] = m a x ( d p [ i ] , d p [ j ] + 1 ) dp[i]=max(dp[i],dp[j]+1) dp[i]=max(dp[i],dp[j]+1)
O(n2)
const int N=5010;
int n;
int a[N],dp[N],ans;
signed main(){cin>>n;for(int i=0;i<n;i++){cin>>a[i];}for(int i=0;i<n;i++){dp[i]=1;//自己是一個數列for(int j=0;j<i;j++){if(a[i]>a[j]){//上升dp[i]=max(dp[i],dp[j]+1);//找之前的數列ans=max(dp[i],ans);}}}cout<<ans<<endl;return 0;
}
O(nlogn)
//O(nlogn)做法
//下降序列
int ans=1,dp[N]={0};
dp[1]=a[1];
for(int k=2;k<=i;k++){if(a[k]<=dp[ans]){//更小的向后取組成序列ans++;dp[ans]=a[k];//下降的序列}else{//跟最后的比不下降 就放前面相當于重開一個序列//dp下降 用greater<>int j=upper_bound(dp+1,dp+1+ans,a[k],greater<int>())-dp;//二分 找第一個小于a[k]的數dp[j]=a[k];//開下降序列}
}
//上升序列
int ans=1,dp[N]={0};
dp[1]=a[1];
for(int k=2;k<=i;k++){if(a[k]>dp[ans]){ans++;dp[ans]=a[k];}else{//dp上升int j=upper_bound(dp+1,dp+1+ans,a[k])-dp;//二分 找第一個大于a[k]的數dp[j]=a[k];}
}
例題
P1020 導彈攔截
構造下降序列找導彈數目,上升序列找系統數目。
二分查找 O(nlogn)做法
細節見代碼。
signed main(){//freopen(".in","r",stdin);//freopen(".out","w",stdout);int i=1;while(cin>>a[i])i++;i--;//能攔截多少導彈int ans=1;dp[1]=a[1];for(int k=2;k<=i;k++){if(a[k]<=dp[ans]){//每一發炮彈都不能高于前一發的高度//比前一發低,記錄數目ans++;dp[ans]=a[k];//構造一個下降的序列}else{//dp下降int j=upper_bound(dp+1,dp+1+ans,a[k],greater<int>())-dp;//二分 找第一個小于a[k]的數 相當于新開一個系統 新開一個下降序列dp[j]=a[k];//開下降序列}}cout<<ans<<endl;//用多少系統int cnt=1;x[1]=a[1];for(int k=2;k<=i;k++){if(x[cnt]<a[k]){//新開一個系統cnt++;x[cnt]=a[k];//x是上升序列}else{int j=lower_bound(x+1,x+cnt+1,a[k])-x;//找第一個大于等于a[k]的系統 能攔截這個炮彈x[j]=a[k];}// for(int m=1;m<=cnt;m++)cout<<x[m]<<' ';// cout<<endl;}cout<<cnt;return 0;
}
P2782 排序+LIS
const int N=2e5+10;
struct fr{int a,b;
}c[N];
int dp[N];
void solve(){int n;cin>>n;forr(i,1,n){cin>>c[i].a>>c[i].b;}sort(c+1,c+1+n,[](fr x,fr y){return x.a<y.a;});//找LISint ans=1;/*//超時forr(i,1,n){dp[i]=1;forr(j,1,i-1){if(c[i].b>c[j].b){dp[i]=max(dp[i],dp[j]+1);ans=max(dp[i],ans);}}}*/dp[1]=c[1].b;forr(i,2,n){if(c[i].b>dp[ans]){ans++;dp[ans]=c[i].b;}else{int j=upper_bound(dp+1,dp+ans+1,c[i].b)-dp;//替換第一個大于c[i].b的dp[j]=c[i].b;}}cout<<ans<<endl;
}
P1091 兩次LIS
const int N=2e5+10;
int dp[N],dpr[N];
void solve(){int n;cin>>n;vector<int>t(n+1);forr(i,1,n){cin>>t[i];}int maxn=0;forr(i,1,n){// dp[i]=1;forr(j,1,i-1){if(t[i]>t[j])dp[i]=max(dp[j]+1,dp[i]);}}reforr(i,1,n){// dpr[i]=1;reforr(j,i+1,n){if(t[i]>t[j])dpr[i]=max(dpr[j]+1,dpr[i]);}}forr(i,1,n){// cout<<dp[i]<<' '<<dpr[i]<<' '<<dp[i]+dpr[i]<<endl;maxn=max(dp[i]+dpr[i]+1,maxn);}cout<<n-maxn<<endl;
}
LCS 最長公共子序列
代碼
狀態轉移方程 d p [ i ] [ j ] = m a x ( d p [ i ? 1 ] [ j ] , d p [ i ] [ j ? 1 ] , d p [ i ? 1 ] [ j ? 1 ] + 1 ) dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1) dp[i][j]=max(dp[i?1][j],dp[i][j?1],dp[i?1][j?1]+1),dp是LCS的長度。
forr(i,1,len){forr(j,1,len){if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}
}
例題
P1435
回文從前面看后面看都是一樣的,所以思路就是將原字符串和逆轉后的字符串找LCS,就是已經回文的。總長減去回文的就是不回文的。
const int N=1e3+10;
int dp[N][N];
void solve(){string s;cin>>s;string rs=string(s.rbegin(),s.rend());int len=s.size();forr(i,1,len){forr(j,1,len){if(s[i-1]==rs[j-1])dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}cout<<len-dp[len][len];
}