动态规划练习题代码

八月 03, 2018 12458

DP 是啥？能吃吗？

本文内容难度：从普及-到普及+/提高

数字三角形问题

给你一个数字三角形，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大，

规定每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;

const int MAXN = 100;

/*
 * 
 * 设f[i][j]表示从第i行第j列走到底部的最优答案
 * 转移方程：f[i][j] = a[i][j] + max(f[i+1][j], f[i+1][j+1])
 * 注意边界
 * 
 */

int f[MAXN][MAXN];
int a[MAXN][MAXN];

int main(int argc, char *const argv[]) {
    int n;
    cin >> n;
    int ans = -23333333;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            f[i][j] = a[i][j] + std::max(f[i-1][j], f[i-1][j-1]);
    		ans = std::max(ans, f[i][j]);
        }
    }
    cout << ans << endl;
}

一维线性动态规划

最长上升子序列

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 10000 + 10;

/*
 *
 * 注意子序列可以不连续
 * 
 * 设f[i]表示目前选第i个数时的最长上升子序列的长度
 * 也就是以第i个数结尾的最长上升子序列的长度
 * f[i] = std::max(1, f[j] + 1)
 * 其中1 <= j < i, a[j] < a[i]
 * 
 * 时间复杂度O(n^2)
 * 
 */

int f[MAXN], a[MAXN];

int main(int argc, char *const argv[]) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j)  {
            if (a[j] < a[i]) f[i] = std::max(1, f[j] + 1);
        }
    }
    cout << f[n];
}

「NOIP2004」合唱队形

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl;
using namespace std;

const int MAXN = 10000 + 10;

/*
 *
 * 正着求一遍最长上升子序列，反着求一遍最长上升子序列
 * （也就是接着求一遍最长下降子序列）
 * 用f数组存最长上升子序列长度
 * 用g数组存最长下降子序列长度
 * 答案是n - max(f[i] + g[i] - 1)
 * 
 */

int f[MAXN], g[MAXN], a[MAXN];

int main(int argc, char *const argv[]) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (a[j] < a[i]) f[i] = std::max(f[i], f[j] + 1);
        }
    }
    for (int i = n; i >= 1; --i) {
        for (int j = n+1; j > i; --j) {
            if (a[j] < a[i]) g[i] = std::max(g[i], g[j] + 1);
        }
    }
    int ans = -23333333;
    for (int i = 1; i <= n; ++i) {
    	ans = std::max(ans, f[i] + g[i] - 1);
    }
    cout << n - ans << endl;
    return 0;
}

线段覆盖

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
/* -- DP 做法 -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1000000 + 10;

/*
 *
 * 先对线段排序
 * 再设f[i]表示前i条线段中不重叠的最大数量
 * f[i] = max(f[i - 1], f[j] + 1)
 * 其中1 <= j < i, 第j条线段的右端点 <= 第i条线段的左端点
 * 
 */

/* 这个时间复杂度洛谷会RE（实为TLE） */

struct Line {
    int left, right;
} line[MAXN];

int f[MAXN];

bool stlCmp(Line x, Line y) {
    return x.right < y.right;
}

int main(int argc, char *const argv[]) {
	ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
    	cin >> line[i].left >> line[i].right;
    	if (line[i].left > line[i].right) swap(line[i].left, line[i].right);
    }
    sort(line + 1, line + 1 + n, stlCmp);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            if (line[j].right <= line[i].left) f[i] = std::max(f[i], f[j] + 1);
        }
    }
    int ans = -23333333;
    for (int i = 1; i <= n; ++i) ans = std::max(ans, f[i]); 
    cout << ans + 1 << endl;	
    return 0;
}

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
/* -- 贪心做法 -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1000000 + 10;

struct Line {
    int left, right;
} line[MAXN];

bool stlCmp(Line x, Line y) {
    return x.right < y.right;    
}

int main(int argc, char *const argv[]) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> line[i].left >> line[i].right;
    sort(line + 1, line + 1 + n, stlCmp);
    int maxRight = -23333333, lines = 0;
    for (int i = 1; i <= n; ++i) {
        if (maxRight <= line[i].left) ++lines, maxRight = line[i].right;
    } 
    cout << lines << endl;
    return 0;
}

多维动态规划

「NOIP2008」传纸条

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;

const int MAX = 50 + 5;

/*/
 *
 * 设dp[i][j][x][y] 表示第一张纸条传到了(i, j)，第二张纸条传到了(x, y)时
 * 的最大答案 
 * dp[i][j][k][l] = std::max(
 *                      std::max(
 *					        dp[i-1][j][k-1][l], 
 *                          dp[i][j-1][k-1][l]
 *					    ), 
 *					    std::max(
 *					        dp[i-1][j][k][l-1], 
 *					        dp[i][j-1][k][l-1]
 *						)
 *					) 
 *					+ a[i][j] 
 *					+ a[k][l] 
 * 
 * 其中 j+1 <= l <= n
 * 最终答案是dp[m][n-1][m-1][n] 
 *
/*/

int dp[MAX][MAX][MAX][MAX];
int n, m, a[MAX][MAX];

inline int getint() {
    int s = 0, x = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') x = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * x;
}

inline void putint(int x, bool returnValue) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x >= 10) putint(x / 10, false);
    putchar(x % 10 + '0');
    if (returnValue) putchar('\n');
}

int main(int argc, char *const argv[]) {
    m = getint(), n = getint();
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            a[i][j] = getint();
        } 
    } 
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= m; ++k) {
                for (int l = j + 1; l <= n; ++l) {
                    dp[i][j][k][l] = std::max(std::max(dp[i-1][j][k-1][l], dp[i-1][j][k][l-1]), std::max(dp[i][j-1][k-1][l], dp[i][j-1][k][l-1])) + a[i][j] + a[k][l];
                }
            }
        }
    }
    putint(dp[m][n-1][m-1][n], true);
    return 0;
}


「NOIP2008 普及」 传球游戏

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;

const int MAXN = 30 + 2;
const int MAXM = 30 + 2;

/*/
 *
 * 设dp[i][j]表示球传到第i次，传到第j个小朋友手中时的方案数
 * dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 
 * 其中dp[0][1] = 1，ans = dp[m][1] 
/*/

int n, m;
int dp[MAXM][MAXN];

inline int getint() {
	int s = 0, x = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') x = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * x;
}

inline void putint(int x, bool returnValue) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x >= 10) putint(x / 10, false);
	putchar(x % 10 + '0');
	if (returnValue) putchar('\n');
}

int main(int argc, char *const argv[]) {
	n = getint(), m = getint();
	dp[0][1] = 1;
	for (int i = 1; i <= m; ++i) {
		dp[i][1] = dp[i-1][2] + dp[i-1][n];
		dp[i][n] = dp[i-1][1] + dp[i-1][n-1];
		for (int j = 2; j < n; ++j) {
			dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];
		}
	}
	putint(dp[m][1], true);
	return 0;
}


背包问题

NASA 的食物计划

普及-，很水

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;

const int MAXN = 50 + 5;
const int MAXVolume = 400 + 10;
const int MAXWeight = 400;

int maxVolume, maxWeight, n;

int f[MAXVolume][MAXWeight];

struct Food {
    int Volume;
    int Weight;
    int Calories;
} food[MAXN];

inline int getint() {
    int s = 0, x = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') x = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * x;
}

inline void putint(int x, bool newLine) {
    if (x < 0) x = -x;
    if (x >= 10) putint(x / 10, false);
    putchar(x % 10 + '0');
    if (newLine) putchar('\n');
}

int main(int argc, char *const argv[]) {
    maxVolume = getint();
    maxWeight = getint();
    n = getint();
    for (int i = 1; i <= n; ++i) {
        food[i].Volume = getint();
        food[i].Weight = getint();
        food[i].Calories = getint();
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = maxVolume; j >= food[i].Volume; --j) {
            for (int k = maxWeight; k >= food[i].Weight; --k) {
                f[j][k] = std::max(f[j][k], f[j - food[i].Volume][k - food[i].Weight] + food[i].Calories);
            }
        }
    }
    printf("%d\n", f[maxVolume][maxWeight]);
    return 0;
}

装箱问题

真 · 背包问题模板题

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 30 + 5;
const int MAXV = 20000; 

int item[MAXN];
int f[MAXN][MAXV];

int main(int argc, char *const argv[]) {
    int n, v;
    cin >> v;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> item[i];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= v; ++j) {
            if (j >= item[i]) f[i][j] = std::max(f[i-1][j], f[i-1][j-item[i]] + item[i]);
            else f[i][j] = f[i-1][j];
        }
    }
    cout << v - f[n][v] << endl; 
    return 0;
}


榨取kkksc03

实在想不通这题为啥是普及/提高-，不应该是普及-吗

所以这就是你评普及/提高-的理由？

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;

const bool __RETURN = true;
const bool __NO_RETURN = false;

const int MAXN = 100 + 10;
const int MAXM = 200 + 10;
const int MAXT = 200 + 10;

int n, m ,T; 

struct Dream {
    int time;
    int cost;
} d[MAXN];

int dp[MAXN][MAXM][MAXT];

/*
 *
 * 设dp[i][j][k]表示当选择第i个愿望，
 * 时间不超过j，金钱不超过k时的最大数量
 * dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-d[i].time][k-d[i].cost] + 1)
 * 其中 j >= d[i].time, k >= d[i].cost 
 *
 */

inline int getint() {
    int s = 0, x = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') x = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * x;
}

inline void putint(int x, bool returnValue) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x >= 10) putint(x / 10, false);
    putchar(x % 10 + '0');
    if (returnValue) putchar('\n');
}

int main(int argc, char *const argv[]) {
    n = getint(), m = getint(), T = getint();
    for (int i = 1; i <= n; ++i) {
        d[i].time = getint();
        d[i].cost = getint();
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int k = 1; k <= T; ++k) {
                if (j >= d[i].time && k >= d[i].cost) {
                    dp[i][j][k] = std::max(dp[i-1][j][k], dp[i-1][j - d[i].time][k - d[i].cost] + 1);
                } else {
                    dp[i][j][k] = dp[i-1][j][k];
                }
            }
        }
    }
    putint(dp[n][m][T], __RETURN); 
    return 0;
}