动态规划专题(一)

这篇文章主要介绍线性dp
以李煜东大神的《算法竞赛进阶指南》和刘汝佳的紫书为蓝本
再加上几道比较复杂的dp题

线性dp暴力求解

//
//  main.cpp
//  POJ2279
//
//  Created by zhangmin chen on 2019/7/31.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>


using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;

const int maxn = 5 + 1;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)

int N[maxn], k;

void solve() {
    //
    _rep(i, 1, k) scanf("%d", &N[i]);
    while(k < 5) N[++k] = 0;
    // _rep(i, 0, 5) debug(N[i]);
    // cout << endl;
    
    llong f[N[1] + 1][N[2] + 1][N[3] + 1][N[4] + 1][N[5] + 1];
    Set(f, 0);
    
    // then DP
    f[0][0][0][0][0] = 1;
    _rep(i, 0, N[1]) _rep(j, 0, N[2]) _rep(k, 0, N[3]) _rep(l, 0, N[4]) _rep(m, 0, N[5]) {
        if(i < N[1]) f[i + 1][j][k][l][m] += f[i][j][k][l][m];
        if(j < N[2] && j < i) f[i][j + 1][k][l][m] += f[i][j][k][l][m];
        if(k < N[3] && k < j) f[i][j][k + 1][l][m] += f[i][j][k][l][m];
        if(l < N[4] && l < k) f[i][j][k][l + 1][m] += f[i][j][k][l][m];
        if(m < N[5] && m < l) f[i][j][k][l][m + 1] += f[i][j][k][l][m];
    }
    
    cout << f[N[1]][N[2]][N[3]][N[4]][N[5]] << endl;
}

int main() {
    freopen("input.txt", "r", stdin);
    while(scanf("%d", &k) == 1 && k) solve();
}

刷表dp(递归求解)模版

OPENJUDGE2760

int dp[maxn][maxn];
int tb[maxn][maxn];
int n;

void init() {
    Set(dp, -1);
    Set(tb, 0);
}

int solve(int i, int j) {
    if(dp[i][j] >= 0) return dp[i][j];
    int& ans = dp[i][j];
    
    return ans = tb[i][j] + (i == n ? 0 : max(solve(i + 1, j), solve(i + 1, j + 1)));
}

int main() {
    freopen("input.txt", "r", stdin);
    init();
    scanf("%d", &n);
    
    _rep(i, 1, n) _rep(j, 1, i) scanf("%d", &tb[i][j]);
    cout << solve(1, 1) << endl;
}

DAG DP模版

class Rec {
public:
    int a, b;
};

Rec rec[maxn];
int G[maxn][maxn];
int n;

int F[maxn];

void init() {
    Set(G, 0);
    Set(F, -1);
}

bool valid(Rec& lhs, Rec& rhs) {
    return (lhs.a < rhs.a && lhs.b < rhs.b) || (lhs.a < rhs.b && lhs.b < rhs.a);
}

// i in j
// G[i][j] = 1
// i -> j

int dp(int x) {
    if(F[x] != -1) return F[x];
    
    int& ans = F[x];
    ans = 1;
    
    _rep(i, 1, n) if(G[x][i]) ans = max(ans, dp(i) + 1);
    return ans;
}

void printAns(int u) {
    printf("%d ", u);
    _rep(i, 1, n) if(G[u][i] && F[u] == F[i] + 1) {
        printAns(i);
        break;
    }
    return;
}

int main() {
    freopen("input.txt", "r", stdin);
    init();
    scanf("%d", &n);
    
    _rep(i, 1, n) scanf("%d%d", &rec[i].a, &rec[i].b);
    _rep(i, 1, n) _rep(j, 1, n) G[i][j] = valid(rec[i], rec[j]);
    
    _rep(i, 1, n) if(F[i] == -1) F[i] = dp(i);
    
    int tid = 0;
    _rep(i, 1, n) if(F[i] > F[tid]) tid = i;
    cout << F[tid] << endl;
    
    printAns(tid);
    cout << endl;
    
}

DAG用解答树刷表法，思路很清晰
DAG

硬币问题

int V[maxn];
int S, N;

int minV[maxn], maxV[maxn];
int d[maxn];
int minCoin[maxn], maxCoin[maxn];

void init() {
    Set(V, 0);
    Set(minV, inf);
    Set(maxV, -inf);
    Set(d, -1);
    Set(minCoin, 0);
    Set(maxCoin, 0);
}

void dp() {
    minV[0] = maxV[0] = 0;
    _rep(i, 1, S) _rep(j, 1, N) {
        if(i >= V[j]) {
            minV[i] = min(minV[i], minV[i - V[j]] + 1);
            maxV[i] = max(maxV[i], maxV[i - V[j]] + 1);
        }
    }
    printf("%d %d\n", minV[S], maxV[S]);
}

// usage:
// minCoin[coinValue] = coinID

void dp2() {
    minV[0] = maxV[0] = 0;
    _rep(i, 1, S) _rep(j, 1, N) if(i >= V[j]) {
        if(minV[i] > minV[i - V[j]] + 1) {
            minV[i] = minV[i - V[j]] + 1;
            minCoin[i] = j;
        }
        if(maxV[i] < maxV[i - V[j]] + 1) {
            maxV[i] = maxV[i - V[j]] + 1;
            maxCoin[i] = j;
        }
    }
    printf("%d %d\n", minV[S], maxV[S]);
}


void printAns(int* d, int S) {
    while(S) {
        printf("%d ", d[S]);
        S -= V[d[S]];
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    init();
    scanf("%d%d", &N, &S);
    
    _rep(i, 1, N) scanf("%d", &V[i]);
    dp2();
    
    
    printAns(minCoin, S);
    cout << endl;
    printAns(maxCoin, S);
}

LCIS问题

LCIS最长公共上升子序列
LCIS

$\textbf{algorithm}$
$f(i, j) \text{ 表示 } A[1\cdots i]\text{的子序列}, B[1\cdots j]\text{的子序列构成的}$
$\text{并且以 } B[j] \text{ 结尾的 LICS 长度}$

$\begin{cases} f(i, j) = f(i - 1, j) && A_i \neq B_j \\ f(i, j) = \max\limits_{0 \leqslant k <j, B_k<B_j} f(i - 1, k) + 1 && A_i = B_j \end{cases}$

$\textbf{for} \ \forall i \in [1, n]$
$\quad \textbf{for} \ \forall j \in [1, m]$
$\quad \quad \textbf{if} \ A_i = B_j$
$\quad \quad \quad \textbf{for} \ \forall k \in [0, j -1], \textbf{if} \ B_k < (B_j \Leftrightarrow A_i)$
$\quad \quad \quad \quad f(i, j) = \max(f(i, j), f(i - 1, k) + 1)$

$\textbf{优化}$
$\textbf{if} \ A_i = B_j$
$\quad \textbf{for} \ \forall k \in [0, j -1] \quad \textbf{if} \ B_{k} < A_{i}$
$\quad \quad \quad f(i, j) = \max(f(i, j), f(i - 1, k) + 1)$

$\textbf{等价于}$

$\begin{gathered} \{\max\limits_{k \in[0, j - 1]}[A_{i-1}][B_0 \cdots B_{j -1}] \ | \ B_k < (B_j \Leftrightarrow A_i)\} \xrightarrow{+1} f(i, j) \\ \ \\ \{f(i-1, k) \ | \ k \in[0, j-1],B_k <A_i\} \xrightarrow{+1} f(i,j)\\ \ \\ \textbf{may}\ \textbf{use} \ \{f(i-1, k) | k \in [0, j-1]\} \cup \{f(i-1,j)\} \ \textbf{update} \ maxv \quad (\text{when } B_j < A_i) \end{gathered}$

$\textbf{利用前缀和思想，用一个}maxv \text{维护上面左边这一项}$

$\begin{gathered} maxv=\max_{k \in [0, j - 1]}\{(A_{i -1}, B_k)\} \\ \ \\ = \max \{ (A_{i-1}, B_0), (A_{i-1}, B_1), \cdots , (A_{i-1}, B_{j-1}) \} \end{gathered}$

$\text{这样可以边对} \ j \ \text{循环边计算}$

$\textbf{for} \ \forall j \in [1, m], \quad \textbf{if} \ B_j < A_i$
$\quad \textbf{update} \ maxv = \max(maxv, f(i - 1, j))$

$\textbf{algorithm}$
$\textbf{for} \ \forall i \in [1, n], maxv = 0$
$\quad \textbf{if} \ B_0 < A_i, maxv = f(i - 1, 0)$
$\quad \quad \textbf{for} \ \forall j \in [1, m]$
$\quad \quad \quad \textbf{if} \ A_i = B_j , \ f(i, j) = maxv + 1$
$\quad \quad \quad \textbf{else} \ f(i, j) = f(i-1, j)$

$\quad \quad \quad \textbf{if} \ B_j < A_i, \ maxv = \max(maxv, f(i-1, j))$

const int maxn = 3000 + 10;
int f[maxn][maxn];
int A[maxn], B[maxn];
int n;

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    _rep(i, 1, n) scanf("%d", &A[i]);
    _rep(i, 1, n) scanf("%d", &B[i]);

    _rep(i, 1, n) {
        int maxv = 0;
        if(B[0] < A[i]) maxv = max(maxv, f[i - 1][0]);

        _rep(j, 1, n) {
            if(A[i] == B[j]) f[i][j] = maxv + 1;
            else f[i][j] = f[i - 1][j];

            if(B[j] > A[i]) maxv = max(maxv, f[i - 1][j]);
        }
    }
    int res = 0;
    _rep(i, 1, n) res = max(res, f[n][i]);
    cout << res << endl;
}

线性dp的序列问题

离散化和中位数优化

离散化和中位数优化是很重要的一种处理思想
POJ3666-01

序列问题的解决模版

POJ3666

POJ3666-02
POJ3666-03

const int maxn = 2000 + 10;
const int inf = 0x3f3f3f3f;

int A[maxn], F[maxn][maxn];
int A2[maxn];
int n;

void init() {
    Set(A, 0);
    Set(A2, 0);
    ///Set(B, 0);
    Set(F, inf);
}

int query(int x, int m) {
    return lower_bound(A2 + 1, A2 + 1 + m, x) - A2;
}

int main() {
    freopen("input.txt", "r", stdin);
    init();
    scanf("%d", &n);

    _rep(i, 1, n) {
        scanf("%d", &A[i]);
        A2[i] = A[i];
    }

    sort(A2 + 1, A2 + 1 + n);
    int m = unique(A2 + 1, A2 + 1 + n) - A2 - 1;
    // id = query(A[i], m)

    F[0][0] = 0;

    _rep(i, 1, n) {
        int val = F[i - 1][0];

        _rep(j, 1, m) {
            int baseline = A2[j];
            val = min(val, F[i - 1][j]);

            F[i][j] = val + abs(A[i] - baseline);
        }
    }

    int ans = inf;
    _rep(j, 1, m) ans = min(ans, F[n][j]);
    cout << ans << endl;

}

带条件的状态转移方程

1 2	在dp的时候先判断valid() if(valid) continue;

对于非法状态，不执行转移

SPOJ-SERVICE

CH5102

const int maxn = 1000 + 10;
const int maxp = 200 + 10;
const int inf = 0x3f3f3f3f;

int L, N;
int cost[maxp][maxp], P[maxn];
int F[maxn][maxp][maxp];

void init() {
    Set(P, 0);
    Set(cost, 0);
    Set(F, inf);
}

void initDP() {
    F[0][1][2] = 0;
    P[0] =3;
}

void dp(int& ans) {
    // debug(f[0])
    _for(i, 0, N) _rep(x, 1, L) _rep(y, 1, L) {
        //debug(F[0][x][y]);
        int z = P[i];

        if(x == z || y == z || x == y) continue;

        F[i + 1][x][y] = min(F[i + 1][x][y], F[i][x][y] + cost[z][P[i + 1]]);
        F[i + 1][P[i]][y] = min(F[i + 1][P[i]][y], F[i][x][y] + cost[x][P[i + 1]]);
        F[i + 1][x][P[i]] = min(F[i + 1][x][P[i]], F[i][x][y] + cost[y][P[i + 1]]);
    }

    _rep(x, 1, L) _rep(y, 1, L) {
        int z = P[N];
        if(x == z || y == z || x == y) continue;

        ans = min(ans, F[N][x][y]);
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);

    while (T--) {
        init();

        scanf("%d%d", &L, &N);

        _rep(i, 1, L) _rep(j, 1, L) cin >> cost[i][j];
        _rep(i, 1, N) scanf("%d", &P[i]);

        // then input finished
        assert(cost[0][0] == 0);
        //assert(P[6] == 5);

        initDP();
        int ans = inf;
        dp(ans);
        cout << ans << endl;
    }
}