一.子序列问题
1.最长公共子序列(LCS)
O(mn)
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| #define N 1005 ll a[N]={0},b[N]={0},dp[N][N]={0}; void solve() { ll m,n;cin >> n >> m; FORLL(i,1,n) cin >> a[i]; FORLL(i,1,m) cin >> b[i]; FORLL(i,1,n) FORLL(j,1,m){ if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } cout << dp[n][m] << endl; }
|
2.最长上升子序列
2.1.DP
$O(n^2)$ 洛谷B3637
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| #define N 10005 ll a[N]={0},dp[N]={0}; void solve() { ll n;cin >> n; FORLL(i,1,n) cin >> a[i]; dp[1]=1;ll ans=0; FORLL(i,2,n){ ll mx=0; FORLL(j,1,i-1) if(a[i]>a[j]) mx=max(mx,dp[j]); dp[i]=mx+1; ans=max(ans,dp[i]); } cout << ans << endl; }
|
2.2.贪心
$O(n\log n)$ 洛谷B3637
贪心:维护当前子序列d,替换序列中不小于a[i]的第一个元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| #define N 10005 ll a[N]={0}; vector<ll> d; void solve() { ll n;cin >> n; FORLL(i,1,n) cin >> a[i]; d.emplace_back(a[1]); FORLL(i,2,n){ if(d.back()<a[i]) d.emplace_back(a[i]); else *lower_bound(ALL(d),a[i])=a[i]; } cout << d.size() << endl; }
|
二.区间DP
$O(n^3)$ NOI1995/LOJ10147
分治:父问题的答案由子问题集中最优解转移
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| #define N 205 ll v[N*2]={0},S[N*2]={0}; ll dpmx[N*2][N*2]={0},dpmn[N*2][N*2]={0}; void solve(){ ll n,t;cin >> n; FORLL(i,1,n){ cin >> v[i]; v[i+n]=v[i]; } FORLL(i,1,n*2) FORLL(j,1,n*2) dpmn[i][j]=INF; FORLL(i,1,n*2) dpmn[i][i]=0; FORLL(i,1,n*2) S[i]=S[i-1]+v[i]; FORLL(len,1,n){ FORLL(i,1,n*2-len+1){ ll j=i+len-1; FORLL(k,i,j-1){ dpmx[i][j]=max(dpmx[i][j],dpmx[i][k]+dpmx[k+1][j]+S[j]-S[i-1]); dpmn[i][j]=min(dpmn[i][j],dpmn[i][k]+dpmn[k+1][j]+S[j]-S[i-1]); } } } ll mx=0,mn=INF; FORLL(i,1,n+1) mx=max(mx,dpmx[i][i+n-1]); FORLL(i,1,n+1) mn=min(mn,dpmn[i][i+n-1]); cout << mn << endl << mx << endl; }
|
三.期望DP
ATC-abc323_e
某点的期望从此前的一段区间内转移
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| #define N 1003 #define X 10004 ll dp[X]={1,0}; ll t[N]={0}; void solve() { ll n,x;cin >> n >> x; FORLL(i,1,n) cin >> t[i]; ll invn=inv(n); FORLL(i,1,x){ FORLL(j,1,n) if(i>=t[j]) addto(dp[i],dp[i-t[j]]); multo(dp[i],invn); } ll re=0; FORLL(i,max(0ll,x-t[1]+1),x) addto(re,dp[i]); cout << multo(re,invn) << endl; }
|
四.DP优化
1. 单调队列优化DP
O(mn) M(m) CF372C
利用单调队列将每次区间DP均摊复杂度降至O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| #define N 305 #define M 150005 ll a[N]={0},b[N]={0},t[N]={0}; ll dp[2][M]={0}; ll n,m,d;int fl=1; ll que[M]={0}; void solve() { cin >> n >> m >> d; FORLL(i,1,m) cin >> a[i] >> b[i] >> t[i]; fl=1; FORLL(i,1,m){ ll l=1,r=0,k=1; FORLL(j,1,n){ for(;k<=min(n,j+(t[i]-t[i-1])*d);k++){ while(r>=l&&dp[fl^1][que[r]]<dp[fl^1][k]) r--; que[++r]=k; } while(r>=l&&que[l]<max(1ll,j-(t[i]-t[i-1])*d)) l++; dp[fl][j]=dp[fl^1][que[l]]+b[i]-abs(a[i]-j); }fl^=1; }fl^=1; ll ans=-INF; FORLL(i,1,n) ans=max(ans,dp[fl][i]); cout << ans << endl; }
|
Reference:OI-Wiki