vijos1111（裸的最長(zhǎng)公共子序列）

鏈接：www.vijos.org/p/1111

題解：好久沒(méi)有寫(xiě)最長(zhǎng)公共子序列了，這題就當(dāng)是復(fù)習(xí)了。求出最長(zhǎng)公共子序列，然后用兩個(gè)單詞的總長(zhǎng)度減去最長(zhǎng)公共子序列

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=101; int dp[maxn][maxn]; char a[maxn],b[maxn]; int main() {while(cin>>a>>b){int n=strlen(a);int m=strlen(b);for(int i=0;i<n;i++) //最長(zhǎng)公共子序列模板 for(int j=0;j<m;j++){if(a[i]==b[j])dp[i+1][j+1]=dp[i][j]+1;elsedp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);}cout<<n+m-dp[n][m]<<endl;}return 0; }

vijos1680（最長(zhǎng)公共子序列的變形）

鏈接：www.vijos.org/p/1680

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int maxn=2001; int dp[maxn][maxn]; char a[maxn],b[maxn]; int minx(int x,int y,int z) {int ab=x;if(y<ab) ab=y;if(z<ab) ab=z;return ab; } int main() {int k;while(cin>>a>>b>>k){int n=strlen(a);int m=strlen(b);for(int i=0;i<n;i++)dp[i+1][0]=dp[i][0]+k;for(int i=0;i<m;i++)dp[0][i+1]=dp[0][i]+k;for(int i=0;i<n;i++)for(int j=0;j<m;j++)dp[i+1][j+1]=minx(dp[i][j+1]+k,dp[i+1][j]+k,dp[i][j]+abs(a[i]-b[j]));cout<<dp[n][m]<<endl;}return 0; }

vijos 1264(最長(zhǎng)公共上升序列）

鏈接：www.vijos.org/p/1264

題解：用dp[i,j]表示a序列的前i個(gè)為結(jié)尾和以b序列的第j個(gè)為結(jié)尾的最長(zhǎng)上升公共序列長(zhǎng)度。則：

dp[i,j]=max{dp[i-1,k]}+1 | (a[i]=b[j]) and (b[k]<b[j])
dp[i,j]=dp[i-1,j] | (a[i]<>b[j])

程序里面在j循環(huán)順帶著就找到了最小的k。對(duì)于所有小于a[i]的b[k]，必定在a[i]=b[j]時(shí)小于b[j]，所以滿足了約束條件。
最后再把i那維給降調(diào)。（為什么沒(méi)有滾動(dòng)，因?yàn)閎[k]<>a[i]，所dp[k]必定沒(méi)有沒(méi)修改）

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=501; int dp[maxn]; int a[maxn],b[maxn]; int main() {int t;cin>>t;while(t--){int n,m;cin>>n;for(int i=1;i<=n;i++)scanf("%d",&a[i]);cin>>m;for(int i=1;i<=m;i++)scanf("%d",&b[i]);memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++) //最長(zhǎng)上升公共序列 {int mx=0;for(int j=1;j<=m;j++){if(a[i]>b[j])mx=max(mx,dp[j]);else if(a[i]==b[j])dp[j]=max(mx+1,dp[j]);}}int mx=0;for(int i=1;i<=m;i++)if(mx<dp[i])mx=dp[i];cout<<mx<<endl;}return 0; }

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

總結(jié)

以上是生活随笔為你收集整理的DP专辑之最长公共子序列及其变形的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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