今天，你讀完這篇文章，普及組的動(dòng)態(tài)規(guī)劃已經(jīng)可以秒了。
最長(zhǎng)公共子序列
求兩個(gè)數(shù)列的最長(zhǎng)公共子序列（Longest Common Subsequence，LCS）的長(zhǎng)度。
數(shù)列 X?和 Y?的最長(zhǎng)公共子序列 Z，是指 Z?既是 X?的子序列，又是 Y?的子序列，而且任意長(zhǎng)度超過(guò) Z?的數(shù)列 Z??都不符合這個(gè)性質(zhì)。
狀態(tài)定義
f[i][j]表示x[1]、x[2]……x[i]和y[1]、y[2]……y[j]的LCS
狀態(tài)轉(zhuǎn)移方程
若x[i]=y[j]，f[i][j]=f[i-1][j-1]+1;
若x[i]!=y[j]，f[i][j]=max(f[i-1][j],f[i][j-1]);
大家可以用滾動(dòng)數(shù)組試試
回文詞
給定一個(gè)字符串，問(wèn)至少需要增加多少個(gè)字符，才能把這個(gè)字符串變成回文詞。一個(gè)字符串是回文詞，是指從前往后看和從后往前看是一樣的。比如：abcba、abccba、bcaacb都是回文詞，但 abc?不是回文詞。
這道題是前一道題的衍生。
假設(shè)給定的字符串為s,將s反轉(zhuǎn)，得到t。那么，答案就是：s長(zhǎng)度-s和t的LCS。這里就不給代碼了
最長(zhǎng)上升子序列
樸素解法
f[i]表示以i結(jié)尾的最長(zhǎng)上升子序列的長(zhǎng)度
按照倒數(shù)第二個(gè)選誰(shuí)分類：
我們先掃描i號(hào)元素前的每個(gè)元素（正向），找出第一個(gè)比i號(hào)元素小的元素k號(hào)。①仍然選i號(hào)元素，f[i]。②選k號(hào)，f[k]+1
但是，這種解法時(shí)間復(fù)雜度為O(N^2)，一但長(zhǎng)度到200，就會(huì)扣分，我們這次就討論O(nlog n)的算法。
優(yōu)化解法
不升子序列最小劃分?jǐn)?shù)
我們用貪心解決這個(gè)問(wèn)題。定義d[i]為第i條不升子序列的最后一個(gè)數(shù)，cnt代表有幾個(gè)子序列
我們先掃描每個(gè)數(shù)字x[i]，再枚舉每一個(gè)子序列，判斷是否能接在某個(gè)子序列后，如果不行，則新增一個(gè)序列即可。
#include <bits/stdc++.h>
#define N 1005
using namespace std;
int n,i,j,d[N],x[N];
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>x[i];
int cnt=0;
for(i=0;i<n;i++){
for(j=0;j<cnt;j++)
if(d[j]>=x[i]) break;
d[j]=x[i];
if(j==cnt) cnt++;
}
cout<<cnt<<endl;
return 0;
}O(N^2)的算法，顯然要優(yōu)化
不妨試試二分
#include <bits/stdc++.h>
#define N 1005
#define INF 2e9
using namespace std;
int n,d[N],x[N];
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>x[i];
fill(d,d+n,INF);
for(i=0;i<n;i++)
*lower_bound(d,d+n,x[i])=x[i];
int cnt=lower_bound(d,d+n,INF)-d;
cout<<cnt<<endl;
return 0;
}大家可能就納悶了：這玩意和LIS有神馬關(guān)系？？？
Dilworth反鏈
LIS為最長(zhǎng)子序列， 那么說(shuō)明一定能找到LIS個(gè)數(shù)，從左往右是遞增的。那么這些樹一定不能放在同一組內(nèi)，不然與不升矛盾。到目前為止，每個(gè)數(shù)單獨(dú)為一組，已經(jīng)開了LIS組了。說(shuō)明任何一種滿足要求的分組，組數(shù)都>=LIS。
這一下子，LIS算法就從O(N^2)降到了O(NlogN)
航線問(wèn)題
這道題是上一道題的衍生。
設(shè)第1行第i個(gè)點(diǎn)對(duì)應(yīng)第2行第f[i]個(gè)點(diǎn)。假設(shè)i<j，則兩條線(i,f[i])和(j,f[j])不相交的充要條件是f[i]<f[j]，于是問(wèn)題變?yōu)榍骹的LIS了，這里就不發(fā)代碼了。
兩個(gè)排列的LCS
我們可以把兩個(gè)排列作相同的置換。如p1:1 5 3 2 4變成1 2 3 4 5，即做置換5→2，2→4，4→5，
于是我們可以將p1置換成1 2 ……n，p2做相同的置換，則問(wèn)題就變?yōu)長(zhǎng)IS了，時(shí)間復(fù)雜度O(N^2)
擺花
原題鏈接：P1077 [NOIP2012 普及組] 擺花 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
我們可以把問(wèn)題抽象化：有?n?個(gè)數(shù)（c1?,c2?,...,cn?），0?ci??ai?,求有多少種方案數(shù)使
就變成經(jīng)典dp了，
然后可以使用前綴和優(yōu)化
乘積最大
原題鏈接：P1018 [NOIP2000 提高組] 乘積最大 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
這道題，我只給代碼，大家自己思考一下
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long f[45][60];
string in;
int n,k;//n位數(shù) k個(gè)乘號(hào)
long long g[45];
long long cut(int l,int r){
long long end = 0;
for(int i = l;i <= r;i++)
end = end * 10 + g[i];
return end;
}
int main(){
cin >> n >> k >> in;
for(int i = 1;i <= n;i++)
g[i] = in[i - 1] - '0';
for(int i=1;i<=n;i++)
f[i][0] = cut(1,i);
for(int i = 2;i <= n;i++){ //枚舉分割為前i位數(shù)字
for(int a = 1;a <= min(i-1,k);a++){ //枚舉有幾個(gè)乘號(hào)
for(int b = a;b < i;b++){ //在第幾位放乘號(hào)
f[i][a] = max(f[i][a],f[b][a-1] * cut(b + 1,i));
}
}
}
cout<<f[n][k];
return 0;
}反逆序?qū)?wèn)題
給定 n,k，求在所有長(zhǎng)度為 n的排列中，有多少排列的逆序?qū)η『脼?k?。
給出表答（懶得打LateX)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int Maxn=10100;
const ll Mod=1e9+7;
int n,k;
ll f[Maxn],sm[Maxn];
int main(){
scanf("%d%d",&n,&k);
f[0]=1;
for(int i=1;i<=n;i++){
sm[0]=f[0];
for(int j=1;j<=k;j++) sm[j]=(sm[j-1]+f[j])%Mod;
for(int j=0;j<=k;j++){
if(i>j) f[j]=sm[j];
else f[j]=(sm[j]-sm[j-i]+Mod)%Mod;
}
}
printf("%lld",f[k]);
return 0;
}今天的題目就是這么簡(jiǎn)單，祝大家早日AC文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-855980.html
彩蛋
給定一個(gè)十進(jìn)制整數(shù)?n，保證?n?的首位不為?00，你必須刪除其中?d?個(gè)數(shù)字，使得留下的數(shù)字最大。請(qǐng)輸出留下的最大數(shù)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-855980.html
到了這里，關(guān)于Peter算法小課堂—線性dp的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
