Dynamic Programming Exercises Beginner 归档题解(3)

#DP #归档 #总结

Published on 2016-02-13

归档地址
最后五题了。

题目

UVa 473 - Raucous Rockers

简单的 01 背包，直接给 DP： $dp[i][j][k]$ 决策前 $i$ 首歌，还剩 $j$ 个满光盘和一张剩余时间为 $t$ 的光盘最多能录多少歌。

dp[i][j][k] = \max\begin{cases}dp[i -1][j][k]\\dp[i - 1][j][k - \text{time}_i], & \text{time}_i <= k\\dp[i - 1][j - 1][t - \text{time}_i] & j > 0\end{cases}

答案是 $dp[n][m - 1][t]$ 。采用滚动数组，那么 $j$ ， $k$ 全部要逆序枚举（一个状态需要比自己小的状态）。题目好像没给数据范围，我试了一下： $n\le800, m\le100, t\le100$ 。

UVa 590 - Always on the run

这个题目就比较水了。 $dp[i][j]$ 第 $i$ 天在城市 $j$ ，到达此状态的最小费用。初始值 $dp[0][0] = 0$ ，其余全是 $\inf$ 。

答案是 $dp[k][n]$ 。

UVa 607 - Scheduling Lectures

还是比较简单，但我的解法比较难懂一些。由于是要尽量少的课程，那么可以贪心求得需要多少课程，然后再 DP 求出最小不满意度。
我没想到贪心，直接裹在一起了，时间复杂度高一些，但代码比较好写。 $dp[i][j]$ 说完 $i - n$ 的主题，当前课程剩余 $j$ 分钟的情况下所能得到的最小结果。结果是一个 pair\ 。决策有两种，一种是剩下的时间教这一主题，一种是不教，具体看代码。
DP 的顺序很重要，一种是逆着来（由 $i + 1 \rightarrow i$ ），一种是正着来（由 $i \rightarrow i + 1$ ），逆着来明显方便一些， $dp[1][0]$ 就是答案。如果正着来，那么就要搜寻一下最优解。
我的做法 $O(nL)$ ，网上贪心的做法 $O(n^{2}k)$ （ $k$ 为最少要教的课数）。

UVa 662 - Fast Food

代码及分析见 UVa 662 - Fast Food。

UVa 672 - Gangsters

又是一道简单题，主要是题意读清楚。改变状态是每一秒末干的事。
$dp[i][j]$ 第 $i$ 秒状态为 $j$ 到最后的最大繁荣值。

dp[i][j] = \max\begin{cases}dp[i + 1][j]\\dp[i + 1][j - 1] + P(i, j) &j > 0\\dp[i + 1][j + 1] & j + 1 \le k\end{cases}

其中 $P(i, j)$ 为第 $i$ 秒状态为 $j$ 得到的繁荣值}。注意边界以及滚动一维即可。

总结

UVa 607 - Scheduling Lectures：DP 有时候值可以携带多个信息，如携带 pair<int, int>，有时候可以降低编程复杂度，但会提升思维复杂度。DP 的顺序同样重要，顺着事情发展的顺序，同样降低复杂度。
UVa 672 - Gangsters：有时候题目给的变量习惯与我们不符合，所以做题的时候要么一开始就处理，要么就适应题目，不要改来改去弄出一堆暗伤。。
这五题都比较简单啊，或许是已经熟悉了 DP 的套路。先找阶段性或是区间性，然后分析状态对后面决策的影响来定状态，做决策的时候要尽量进行优化。还可以滚动数组。有时候 DP 的顺序很重要，要分析正反顺序哪一个方便可行。
其实动态规划就是通过小规模的问题的解答来解决大问题，动归的状态反应了问题的实质，决策反映了问题的求解策略。

代码

代码基本上是从 $0$ 开始的，分析中基本从 $1$ 开始。

UVa 473 - Raucous Rockers

//  Created by Sengxian on 2/13/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 473 背包
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n');
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}


const int maxn = 800 + 3, maxm = 100 + 3, maxt = 100 + 3;
int ti[maxn], n, t, m;
int dp[maxm][maxt];
//dp[i + 1][j][k] 决策前 i 首歌，还剩 j 个满光盘和一张剩余时间为 t 的光盘最多能录多少歌

int solve() {
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < n; ++i)
        for(int j = m - 1; j >= 0; --j)
            for(int k = t; k >= 0; --k) {
                //总是可以选择不录，由于滚动了，不做操作
                //选择录
                if(k >= ti[i]) dp[j][k] = max(dp[j][k], dp[j][k - ti[i]] + 1);
                else if(j) dp[j][k] = max(dp[j][k], dp[j - 1][t - ti[i]] + 1);
            }
    return dp[m - 1][t];
}

int main() {
    int caseNum = ReadInt();
    while(caseNum--) {
        n = ReadInt(), t = ReadInt(), m = ReadInt();
        for(int i = 0; i < n; ++i) ti[i] = ReadInt();
        printf("%d\n", solve());
        if(caseNum) br
    }
    return 0;
}

UVa 590 - Always on the run

//  Created by Sengxian on 2/14/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 590 DP
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n');
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 10 + 3, maxk = 1000 + 3, maxd = 30 + 3, INF = 0x3f3f3f3f;
int cost[maxn][maxn][maxd], cnt[maxn][maxn];
int n, k, dp[maxk][maxn];

//dp[j + 1][i] 第 (j + 1) 天在第 i 个城市，到达此状态的最小费用
int solve() {
    memset(dp[0], INF, sizeof(dp[0]));
    dp[0][0] = 0;
    for(int d = 0; d < k; ++d)
        for(int i = 0; i < n; ++i) {
            dp[d + 1][i] = INF;
            for(int u = 0; u < n; ++u) {
                if(i == u || cost[u][i][d % cnt[u][i]] == 0) continue;
                dp[d + 1][i] = min(dp[d + 1][i], dp[d][u] + cost[u][i][d % cnt[u][i]]);
            }
        }
    return dp[k][n - 1];
}

int main() {
    int caseNum = 0;
    while(n = ReadInt(), k = ReadInt(), n + k) {
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j) {
                if(i == j) continue;
                cnt[i][j] = ReadInt();
                for(int k = 0; k < cnt[i][j]; ++k) cost[i][j][k] = ReadInt();
            }
        int res = solve();
        printf("Scenario # %d\n", ++caseNum);
        if(res >= INF) puts("No flight possible.");
        else printf("The best flight costs %d.\n", res);
        br
    }
    return 0;
}

UVa 607 - Scheduling Lectures

//  Created by Sengxian on 2/14/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 607 DP
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n');
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

typedef pair<int, int> state;
const int maxn = 1000 + 3, maxl = 500 + 3;
const state null = state(-1, -1), INF = state(0x3f3f3f3f, 0x3f3f3f3f);
int t[maxn], L, C, n;
state dp[maxn][maxl];

inline int di(int x) {
    if(x == 0) return 0;
    if(x <= 10) return -C;
    return (x - 10) * (x - 10);
}

//决策 cur ~ n 的主题，当前课程剩余 left 分钟的情况下 所能得到的最小结果
state DP(int cur, int left) {
    if(cur == n) return state(1, di(left)); //一定要注意结算最后一节课！
    if(dp[cur][left] != null) return dp[cur][left];
    state &res = dp[cur][left] = INF;
    //教授这一主题
    if(left >= t[cur]) res = min(res, DP(cur + 1, left - t[cur]));
    //抛弃剩下的时间
    state st = DP(cur + 1, L - t[cur]);
     if(cur) st.first++; //注意一开始剩下 0 分钟不能算一节课！
    st.second += di(left);
    res = min(res, st);
    return res;
}

int main() {
    int caseNum = 0;
    while(n = ReadInt(), n) {
        if(caseNum) br
        L = ReadInt(), C = ReadInt();
        for(int i = 0; i < n; ++i) t[i] = ReadInt(), fill(dp[i], dp[i] + L + 1, null);
        state ans = DP(0, 0);
        printf("Case %d:\nMinimum number of lectures: %d\nTotal dissatisfaction index: %d\n", ++caseNum, ans.first, ans.second);
    }
    return 0;
}

UVa 672 - Gangsters

//  Created by Sengxian on 2/14/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 672 DP
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n');
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}
const int maxn = 100 + 3, maxk = 100 + 3, maxt = 30000 + 3;
vector<int> G[maxt];
int n, k, t, si[maxn], pi[maxn];
int dp[2][maxk], cnt[maxk];

//dp[i][j] 第 i 秒状态为 j 到最后的最大繁荣值
int solve() {
    memset(dp[(t + 1) & 1], 0, sizeof(dp[(t + 1) & 1]));
    for(int i = t; i >= 0; --i) {
        int _i = i & 1;
        fill(cnt, cnt + k + 1, 0);
        for(int j = 0; j < G[i].size(); ++j)
            cnt[si[G[i][j]]] += pi[G[i][j]];
        for(int j = 0; j <= k; ++j) {
            dp[_i][j] = dp[!_i][j];
            if(j) dp[_i][j] = max(dp[_i][j], dp[!_i][j - 1]);
            if(j + 1 <= k) dp[_i][j] = max(dp[_i][j], dp[!_i][j + 1]);
            dp[_i][j] += cnt[j];
        }
    }
    return dp[0][0];
}

int main() {
    int caseNum = ReadInt();
    while(caseNum--) {
        n = ReadInt(), k = ReadInt(), t = ReadInt();
        for(int i = 0; i <= t; ++i) G[i].clear();
        for(int i = 0; i < n; ++i) G[ReadInt()].push_back(i);
        for(int i = 0; i < n; ++i) pi[i] = ReadInt();
        for(int i = 0; i < n; ++i) si[i] = ReadInt();
        printf("%d\n", solve());
        if(caseNum) br
    }
    return 0;
}

UVa 662 - Fast Food Dynamic Programming Exercises Beginner 归档题解(2)

Sengxian's Blog