对动态规划问题中的思维方式
举了一些例子

多阶段决策问题

注意状态表示

UVA10618

UVA10618
UVA10618

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

const int maxn = 70 + 5;
const int inf = 0x3f3f3f3f;
char str[maxn];

const int UP = 0;
const int LEFT = 1;
const int RIGHT = 2;
const int DOWN = 3;

// === init ID ==
map<char, int> ID;
void initID() {
    ID['U'] = 0;
    ID['L'] = 1;
    ID['R'] = 2;
    ID['D'] = 3;
}
// == init finished ==

// == data structure
const char footch[] = ".LR";
int d[maxn][4][4][3];
int act[maxn][4][4][3];

// == compute energy ==
// (f0 != f), return 1
int energy(int a, int ta) {
    if(a == ta) return 3;
    if(a + ta == 3) return 7;
    return 5;
}

int energy(int a, int& ta, int b, int& tb, int f0, int f, int t) {
    ta = a, tb = b;
    if(f == 1) ta = t;
    else if(f == 2) tb = t;

    if(ta == tb) return -1;
    if(ta == RIGHT && tb == LEFT) return -1;
    if(ta == RIGHT && tb != b) return -1;
    if(tb == LEFT && ta != a) return -1;

    int ans = 0;
    if(f == 0) ans = 0;
    else if(f != f0) ans = 1;
    else {
        if(f == 1) ans = energy(a, ta);
        else if(f == 2) ans = energy(b, tb);
    }
    return ans;
}

void update(int i, int a, int b, int f0, int f, int t) {
    int ta, tb;
    int e = energy(a, ta, b, tb, f0, f, t);
    if(e < 0) return;

    int& ans = d[i][a][b][f0];
    int cost = d[i+1][ta][tb][f] + e;

    if(chmin(ans, cost)) {
        act[i][a][b][f0] = f * 4 + t;
    }

}
// == compute finished ==

void initdp() {
    memset(d, 0, sizeof(d));
}

void dp(int n) {
    for(int i = n - 1; i >= 0; i--) {
        _for(a, 0, 4) _for(b, 0, 4) if(a != b) {
            _for(f0, 0, 3) {
                d[i][a][b][f0] = inf;

                if(str[i] == '.') {
                    update(i, a, b, f0, 0, 0);
                    _for(t, 0, 4) {
                        update(i, a, b, f0, 1, t);
                        update(i, a, b, f0, 2, t);
                    }
                }
                else {
                    update(i, a, b, f0, 1, ID[str[i]]);
                    update(i, a, b, f0, 2, ID[str[i]]);
                }
            }
        }
    }
}

void printAns(const int n, int i, int a, int b, int f0) {
    if(i == n) return;

    int f = act[i][a][b][f0] / 4;
    int t = act[i][a][b][f0] % 4;
    printf("%c", footch[f]);

    int na = a, nb = b, nf = f;
    if(f == 1) na = t;
    else if(f == 2) nb = t;

    printAns(n, i + 1, na, nb, nf);
}

void init() {
    memset(d, 0, sizeof(d));
    memset(act, 0, sizeof(act));
}

int main() {
    freopen("input.txt", "r", stdin);

    initID();
    while (scanf("%s", str) == 1) {
        if(str[0] == '#') break;

        init();
        // then dp

        initdp();
        int n = strlen(str);
        dp(n);
        printAns(n, 0, LEFT, RIGHT, 0);
        printf("\n");
    }
}

二分图统计dp：背包模型

ZOJ1462

algorithm\textbf{algorithm}

  • 很容易想到这是一个二分图
    进行黑白二染色，如果非二分图，return false\text{return false}
    如果是二分图，考虑 dpdp 计数

  • 进行黑白二染色之后，每个连通分量的队伍安排，是确定的
    黑的只能去黑的组，白的只能去白的组

    • 很显然根据连通分量划分 dp 阶段
      for ∀i∈[1,cc],team(i,0),team(i,1)\textbf{for} \ \forall i \in [1, cc], team(i, 0), team(i, 1)
      分别表示连通分量 ii 中两种染色的点有多少

    • 可以计算出每个连通分量两个组人员的差
      diff(i)=team(i,0)−team(i,1)\textbf{diff}(i) = team(i, 0) - team(i, 1)

    • d(i,j)d(i, j) 表示第 ii 个连通分量两组人的差异是 jj

      d(i,j)⟶{d(i+1,j+diff(i))d(i+1,j−diff(i))d(i, j) \longrightarrow \begin{cases} d(i+1, j + \text{diff}(i)) \\ d(i+1, j - \text{diff}(i)) \end{cases}

      这里 d(i,j)d(i, j) 表示这个状态是否存在
      start: d(0,0)=1\text{start: } d(0, 0) = 1
      因为有负值存在，这里我们算的时候，都加上一个 nn 做调整
      j→j+nj \to j+n

  • 如何输出？
    dp(0→cc−1),如果能够存在某个 diff 差异=ansdp(0 \rightarrow cc-1), \text{如果能够存在某个 diff 差异} = ans
    d(cc,ans)=1d(cc, ans) = 1

    for ans=[0⋯n]\textbf{for} \ ans = [0 \cdots n]
          ~~~~~~if d(cc,ans)=1,print(ans), return\textbf{if} \ d(cc, ans) = 1, \text{print}(ans), \ \textbf{return}

    print(ans):\textbf{print}(ans):
    for ∀i=cc−1 downto 0\textbf{for} \ \forall i = cc-1 \text{ downto } 0
          ~~~~~~if d(i,ans−diff(i))=1,ans−diff(i),[team0]\textbf{if} \ d(i, ans-\text{diff}(i))=1, ans-\text{diff}(i), [team0]
          ~~~~~~if d(i,ans+diff(i))=1,ans+diff(i),[team1]\textbf{if} \ d(i, ans+\text{diff}(i))=1, ans+\text{diff}(i), [team1]
    [team0],[team1] is the answer[team0], [team1] \text{ is the answer}

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

const int maxn = 100 + 10;
int n;
int G[maxn][maxn];

void initG() {
    memset(G, 0, sizeof(G));
}

int color[maxn], cc = 0;
vector<int> team[maxn][2];
int diff[maxn];

bool dfs(int u, int c, int cc) {
    color[u] = c;
    team[cc][c-1].push_back(u);

    _for(v, 0, n) {
        if(v == u || (G[u][v] && G[v][u])) continue;
        if(color[v] > 0 && color[v] == color[u]) return false;
        if(!color[v] && !dfs(v, 3-c, cc)) return false;
    }
    return true;
}

bool build() {
    cc = 0;
    _for(u, 0, n) {
        if(!color[u]) {
            team[cc][0].clear();
            team[cc][1].clear();

            if(!dfs(u, 1, cc)) return false;
            diff[cc] = team[cc][0].size() - team[cc][1].size();
            //debug(diff[cc]);
            cc++;
        }
    }
    return true;
}

// == dp ==
int d[maxn][maxn << 1];

void dp() {
    d[0][0+n] = 1;
    _for(i, 0, cc) {
        for(int j = -n; j <= n; j++) if(d[i][j+n]) {
            d[i+1][j+n+diff[i]] = 1;
            d[i+1][j+n-diff[i]] = 1;
        }
    }
}
// == dp finished ==

// == then solve ==
void print_ans(int ans) {
    vector<int> team0, team1;

    int flag = 0;
    for(int i = cc - 1; i >= 0; i--) {
        if(d[i][ans+n-diff[i]]) {
            flag = 0;
            ans -= diff[i];
        }
        else {
            flag = 1;
            ans += diff[i];
        }

        for(auto x : team[i][flag]) team0.push_back(x);
        for(auto x : team[i][flag^1]) team1.push_back(x);
    }

    printf("%d", (int)team0.size());
    for(auto x : team0) printf(" %d", x+1);
    printf("\n");

    printf("%d", (int)team1.size());
    for(auto x : team1) printf(" %d", x+1);
    printf("\n");
}

void solve() {
    _rep(ans, 0, n) {
        if(d[cc][ans+n]) {
            print_ans(ans);
            return;
        }
        if(d[cc][-ans+n]) {
            print_ans(-ans);
            return;
        }
    }
}
// == solve finished ==

void init() {
    memset(color, 0, sizeof(color));
    _for(i, 0, maxn) _for(j, 0, 2) team[i][j].clear();
    memset(diff, 0, sizeof(diff));
    memset(d, 0, sizeof(d));
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;

    while (kase--) {
        init();
        initG();

        scanf("%d", &n);
        _for(i, 0, n) {
            int v;
            while (scanf("%d", &v) && v) G[i][v-1] = 1;
        }

        // input finished

        if(n == 1 || !build()) {
            printf("No solution\n");
            if(kase) printf("\n");
            continue;
        }

        // then dp
        dp();
        solve();

        if(kase) printf("\n");
    }
}

总结，本例中的图本来就是一个二分图
d(i+1,j+diff(i))=1d(i+1, j+\text{diff}(i))=1 的连通分量，其中的点属于 team1，那么
d(i+1,j−diff(i))=1d(i+1, j-\text{diff}(i))=1 的连通分量，其中的点一定属于 team2
diff\text{diff} 表示每个连通分量之间 不同染色点之间的差异

爬楼梯类的经典问题

UVA10934
algorithm\textbf{algorithm}
d(i,j)d(i, j) 表示当前阶段是检查球 ii, 进行到第 jj 次实验
此时最后处在的楼层数， 不妨记为 ansans

d(i,j)=∑{d(i−1,j−1)+1第 i 个气球在第 j 层破了d(i,j−1)气球没有破，那么在 ans 的基础上，还需要检查 i 个气球，再进行 j−1 次实验d(i, j) = \sum \begin{cases} d(i-1, j-1)+1 && \text{第 } i \text{ 个气球在第 } j \text{ 层破了} \\ d(i, j-1) && \text{气球没有破，那么在 ans 的基础上，还需要检查 } i \text{ 个气球，再进行 } j-1 \text{ 次实验} \end{cases} 

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
27
28
29
30
31
32
33
34
35
36
37

const int maxn = 100;
const int maxk = 63;

ll d[maxn+1][maxk+1];

void initdp() {
    memset(d, 0, sizeof(d));
}

void dp() {
    _rep(i, 1, maxn) _rep(j, 1, maxk) {
        d[i][j] = d[i-1][j-1] + 1 + d[i][j-1];
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    initdp();
    dp();

    int k;
    ll n;

    while (cin >> k >> n && k) {
        int ans = -1;
        _rep(j, 1, maxk) {
            if(d[k][j] >= n) {
                ans = j;
                break;
            }
        }

        if(ans < 0) printf("More than %d trials needed.\n", maxk);
        else printf("%d\n", ans);
    }
}

动态规划中未来费用的计算

例1

处理一系列区间问题的时候
[l1,r1][l_1, r_1] 和 [l2,r2][l_2, r_2] 的代价如果可以用一种线性关系来表示
比如你当前处于区间 [li,ri][l_i, r_i], 移动到这个区间的代价是一个线性函数
f(i)=k⋅d(i)f(i) = k\cdot d(i)
这类区间 dp\text{dp} 可以用未来费用计算来解决

UVALive3181

LA3181

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

const int maxn = 1000 + 5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-4;

double d[maxn][maxn][2];
double sum[maxn];
int n;
double x0, v;

struct A {
    double x;
    double c;
    double d;

    A() {}
    A(double x, double c, double d) : x(x), c(c), d(d) {}

    bool operator< (const A& rhs) const {
        return x < rhs.x;
    }
} a[maxn];

void initdp() {
    memset(d, -1, sizeof(d));
}

double cost(double x1, double x2, int l, int r) {
    return fabs(x1-x2) / v * (sum[l-1] + sum[n] - sum[r]);
}

double dp(int l, int r, int flag) {
    double& ans = d[l][r][flag];
    if(ans >= 0) return ans;

    if(l == r) {
        if(fabs(a[l].x - x0) <= eps) {
            ans = 0;
            return ans;
        }
        else {
            ans = inf;
            return ans;
        }
    }

    ans = inf;
    if(flag == 0) {
        ans = min(ans, dp(l+1, r, 0)+ cost(a[l+1].x, a[l].x, l+1, r) + a[l].c);
        ans = min(ans, dp(l+1, r, 1) + cost(a[r].x, a[l].x, l+1, r) + a[l].c);
    }
    if(flag) {
        ans = min(ans, dp(l, r-1, 1) + cost(a[r-1].x, a[r].x, l, r-1) + a[r].c);
        ans = min(ans, dp(l, r-1, 0) + cost(a[l].x, a[r].x, l, r-1) + a[r].c);
    }

    return ans;
}

void init() {
    memset(sum, 0, sizeof(sum));
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d%lf%lf", &n, &v, &x0) == 3 && n) {
        init();

        _rep(i, 1, n) {
            scanf("%lf%lf%lf", &a[i].x, &a[i].c, &a[i].d);
        }
        a[++n] = A(x0, 0, 0);
        sort(a + 1, a + 1 + n);

        _rep(i, 1, n) sum[i] = sum[i - 1] + a[i].d;
        //debug(sum[n]);

        // then dp
        initdp();
        double ans = min(dp(1, n, 0), dp(1, n, 1));
        //debug(ans);
        printf("%.0lf\n", floor(ans));
    }
}

例2

UVA1625
UVA1625

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
const int maxn = 5000 + 10;
const int inf = 0x3f3f3f3f;
const int maxs = 256;
char p[maxn], q[maxn];
int n, m;

int sp[maxs+1], ep[maxs+1];
int sq[maxs+1], eq[maxs+1];

void prework() {
    _rep(i, 1, n) {
        sp[p[i]] = min(sp[p[i]], i);
        ep[p[i]] = i;
    }
    _rep(i, 1, m) {
        sq[q[i]] = min(sq[q[i]], i);
        eq[q[i]] = i;
    }
}

int f[2][maxn], cnt[2][maxn];
int k = 0;

void initdp() {
    memset(f, 0, sizeof(f));
    memset(cnt, 0, sizeof(cnt));
    k = 0;
}

void update(int i, int j) {
    if(i) {
        cnt[k][j] = cnt[k^1][j];
        if(i == sp[p[i]] && j < sq[p[i]]) cnt[k][j]++;
        if(i == ep[p[i]] && j >= eq[p[i]]) cnt[k][j]--;
        //debug(cnt[k][j]);
    }
    if(j) {
        cnt[k][j] = cnt[k][j - 1];
        if(j == sq[q[j]] && i < sp[q[j]]) cnt[k][j]++;
        if(j == eq[q[j]] && i >= ep[q[j]]) cnt[k][j]--;
    }
}

void dp() {
    _rep(i, 0, n) {
        _rep(j, 0, m) {
            if(i == 0 && j == 0) continue;

            int v1 = inf, v2 = inf;
            if(i) v1 = f[k^1][j] + cnt[k^1][j];
            if(j) v2 = f[k][j - 1] + cnt[k][j - 1];
            f[k][j] = min(v1, v2);

            update(i, j);
        }
        k ^= 1;
    }
}


void init() {
    Set(sp, inf);
    Set(ep, 0);
    Set(sq, inf);
    Set(eq, 0);

    n = strlen(p + 1);
    m = strlen(q + 1);
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;

    while (kase--) {
        scanf("%s", p + 1);
        scanf("%s", q + 1);

        // prework
        init();
        prework();

        // dp
        initdp();
        dp();
        printf("%d\n", f[k^1][m]);
    }
}

dp水题

水题能写出状态转移方程都不难
UVALive4256

d(i,x)=min⁡(y=x) or G(x,y)=1{d(i−1,y)+(x=?stri)}d(i, x) = \min_{(y = x) \ \textbf{or} \ G(x, y)=1} \{d(i-1, y) + (x =? str_i)\} 

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
const int maxn = 200 + 10;
const int inf = 0x3f3f3f3f;
int G[maxn][maxn];

int n, m, len;

vector<int> data(maxn);
int d[maxn][maxn];

void initdp() {
    memset(d, inf, sizeof(d));
    //d[0][0] = 0;
    _rep(i, 1, n) d[1][i] = (i != data[1]);
}

void dp() {
    _rep(i, 2, len) {
        _rep(x, 1, n) {
            int add = (x != data[i]);

            _rep(y, 1, n) {
                if(y == x || G[x][y] || G[y][x]) {
                    chmin(d[i][x], d[i - 1][y] + add);
                }
            }
        }
    }
}

void init() {
    memset(G, 0, sizeof(G));
    data.clear();
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;

    while (kase--) {
        init();
        scanf("%d%d", &n, &m);

        _rep(i, 1, m) {
            int u, v;
            scanf("%d%d", &u, &v);
            G[u][v] = G[v][u] = 1;
        }


        scanf("%d", &len);
        _rep(i, 1, len) {
            int x;
            scanf("%d", &x);
            data[i] = x;
        }

        //_rep(i, 1, len) debug(data[i]);
        // then dp
        initdp();
        dp();
        int ans = inf;
        _rep(x, 1, n) ans = min(ans, d[len][x]);
        printf("%d\n", ans);
    }
}