HDOJ6968 I love exam【线性DP】

题目链接：HDU6968 I love exam

题意

​ 有 ​ 门科目需要考试，而 ​ 所有科目都初始分数为 ​。但有 ​ 套复习资料，对于复习资料 ​，它可以提高对应课程 ​ 的分数（最多提高到 ​），需要花费 ​ 天，且每套复习资料是一次性的。现在距离考试还有 ​ 天，在允许最多挂 ​ 门课程（分数小于 ​）的情况下，求 ​ 能获得的最大的分数，若不能满足则输出 。

题解

不妨给每个科目一个哈希值，然后用背包问题算出每个科目在前 天能获得的最大分数，最后枚举从哪门课开始复习，取最大值即可。

定义dp1[i][j]为哈希值为 ​ 的课程，获得分数 所需要花费的天数，dp2[i][j]为哈希值为 的课程，前 天所能获得的最大分数，dp3[i][j]为前 天，所挂科目数为 的最大分数。

用 01 背包求出获得分数 ​​​​ 所需要花费的最小天数，这里要注意最大的背包容量从 ​​​ 开始，而不是 ​​​，因为设当前分数为 ​​，如果还有一份分数为 ​​ 的资料，那么他能获得的分数为 ​​，即最大上限。然后再从 ​​~​ 所需要的最少天数转移到 。这样就获得了第 组分数为 所需要的最少天数了。定义状态转移方程：

为了到达分数 ​，至少需要 天，也就是每天 分，用刚刚的dp1转移到dp2，即到达分数 所需天数如果小于 的话，就更新。

接着枚举从一门课程开始预习复习，假设当前从课程 开始，定义状态转移方程：

前 ​​ 天、挂了 ​ 科所获得分一定从同样的天数、挂了 ​ 科转移而来。再挂科数相同都为 ​ 的情况下，枚举天数 ​，若前 天获得得分数不小于 ，说明它可以从前 天转移而来， 取最大值即可；如果小于 ，但 不为 ，即还允许挂科，那么可以从前 天，挂 门科转移而来。

最后答案就是dp3[i][j]的最大值。

参考代码

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
//参考std
#include <iostream>
#include <map>
#include <string>
#include <cstring>
#include <vector>

using namespace std;

const int N = 55;
const int inf = 0x3f3f3f3f;
int dp1[110][110], dp2[55][510], dp3[510][5];
int n, m, t, p;
string s;
map<string, int> id;
struct node {
	int x, y;
};
vector<node> v[N];

void solve() {
	
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> s;
		id[s] = i;
	}
	cin >> m;
	for (int i = 1; i <= m; ++i) {
		int xx, yy;
		cin >> s >> xx >> yy;
		v[id[s]].push_back((node){xx, yy}); 
	}
	cin >> t >> p;
	
	memset(dp1, 0x3f, sizeof(dp1));
	memset(dp2, 0, sizeof(dp2));
	memset(dp3, -0x3f, sizeof(dp3));
	
	for (int i = 1; i <= n; ++i) {
		dp1[i][0] = 0;
		int len = v[i].size();
		for (int j = 0; j < len; ++j) {
			for (int k = 109; k >= v[i][j].x; --k) { 
				dp1[i][k] = min(dp1[i][k], dp1[i][k-v[i][j].x] + v[i][j].y);
			}
		}
		for (int k = 109; k >= 100; --k) {
			dp1[i][k] = min(dp1[i][k+1], dp1[i][k]);
		}
		
		for (int k = 1 ; k <= 100; ++k) {
			if (dp1[i][k] > 500) continue;
			dp2[i][dp1[i][k]] = max(dp2[i][dp1[i][k]], k);
		}
	}
	
	dp3[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = t; j >= 1; --j) {
			for (int k = p; k >= 1; --k)
				dp3[j][k] = dp3[j][k-1];
			
			dp3[j][0] = -inf;
			for (int k = 0; k <= p; ++k) {
				int up = min(dp1[i][100], j);
				for (int l = 1; l <= up; ++l) {
					if (dp2[i][l] >= 60) dp3[j][k] = max(dp3[j][k], dp3[j - l][k] + dp2[i][l]);
					else if (k > 0) dp3[j][k] = max(dp3[j][k], dp3[j-l][k-1] + dp2[i][l]); 
				}
			}
		}
		dp3[0][0] = -inf;
	}
	
	int ans = -1;
	for (int i = 1; i <= t; ++i) {
		for (int j = 0; j <= p; ++j) {
			ans = max(dp3[i][j], ans);
		}
	}
	cout << ans << endl;
	id.clear();
	for (int i = 1; i <= n; ++i) v[i].clear();
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	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
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
#include <iostream>
#include <cstring>
#include <map>
#include <vector>
#include <string>

using namespace std;

int n, m, t, p;
struct node {
	int x, y;
};
vector<node> v[55];
map<string, int> id;
int f[55][510]; // 第i门科目，前j天能获得的最大分数
int dp[55][510][5]; // 前i门科目，前j天，挂了k科能获得的最大分数

void solve() {
	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		string str; cin >> str;
		id[str] = i;
	}
	cin >> m;
	for (int i = 1; i <= m; i++) {
		string str;
		int xx, yy;
		cin >> str >> xx >> yy;
		v[id[str]].push_back((node){xx, yy});
	}
	cin >> t >> p;
		
	memset(f, 0, sizeof(f));
	memset(dp, -0x3f, sizeof(dp));
		
	for (int i = 1; i <= n; i++) {
        // 01背包计算f
		for (int j = 0; j < v[i].size(); j++) {
			for (int k = t; k >= v[i][j].y; k--) {
				f[i][k] = max(f[i][k], f[i][k - v[i][j].y] + v[i][j].x);
				f[i][k] = min(f[i][k], 100);
			}
		}
	}
		
	dp[0][0][0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = t; j; j--) {
			for (int k = t; k >= j; k--) {
				for (int l = 0; l <= p; l++) {
                    if (f[i][j] >= 60) dp[i][k][l] = max(dp[i][k][l], dp[i-1][k-j][l] + f[i][j]);
					else if (l) dp[i][k][l] = max(dp[i][k][l], dp[i-1][k-j][l-1] + f[i][j]);
				}
			}
		}
	}
	
	int ans = -1;
	for (int i = 1; i <= t; i++) {
		for (int j = 0; j <= p; j++) {
			ans = max(ans, dp[n][i][j]);
		}
	}
	cout << ans << endl;
	
	id.clear();
	for (int i = 1; i <= n; i++) v[i].clear();
}

int main() {
    
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int t; 
	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

复杂度分析

  • 时间复杂度：。
  • 空间复杂度：。