一.子序列问题

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
/*----------Code Area----------*/
#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];
    }//最长不降子序列改成upper_bound
    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;//Init
    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;//根据长度和i算出j
            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};//歌曲在t时刻切换的概率
ll t[N]={0};
void solve()
{
    ll n,x;cin >> n >> x;
    FORLL(i,1,n) cin >> t[i];
    ll invn=inv(n);//1/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;//单调队列优化DP：维护上一状态的有效区间内的最大值的下标
            }
            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