HDU6968 I love exam（哈希/线性DP）

比赛时没看出来是背包，还以为是可反悔贪心……补题时看std状态转移方程也看的人麻……原来我还在门外，或者已经入土了……

题目链接：HDU6968 I love exam

题目描述：

$Z$​ 有 $n$​ 门科目需要考试，而 $Z$​ 所有科目都初始分数为 $0$​。但有 $m$​ 套复习资料，对于复习资料 $i$​，它可以提高对应课程 $x_i$​ 的分数（最多提高到 $100$​），需要花费 $y_i$​ 天，且每套复习资料是一次性的。现在距离考试还有 $t$​ 天，在允许最多挂 $p$​ 门课程（分数小于 $60$​）的情况下，求 $Z$​ 能获得的最大的分数，若不能满足则输出 $-1$。其中，$n\le 50$，$m\le 15000$，$1\le x_i,y_i\le 10$，$1\le t\le 500$，$0\le p\le 3$​。

输入数据格式为，第一行输入测试样例组数 $T$​​​​​​​​。对于每组测试样例，第一行输入一个整数 $n$​​​​​​​，表示课程总数。第二行输入 $n$​​​​​ 个长度不超过 $15$​​​​ 的字符串，表示课程名。第三行输入一个整数 $m$​​​，表示它获得的复习资料。接下来 $m$​​​ 行，输出一串字符串，两个整数 $x$​​​，$y$​，表示复习资料对应的课程名以及它能提高的分数和所需要花费的天数。最后两行，输入两个整数 $t$​，$p$，表示他能复习的天数以及允许挂科的总数的最大值。

输出数据的格式为，输出仅一行，若有可行解，输出他能获得的最大分数，否则输出 $-1$。

题目解析：

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

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

用 01 背包求出获得分数 $j$​​​​ 所需要花费的最小天数，这里要注意最大的背包容量从 $109$​​​ 开始，而不是 $100$​​​，因为设当前分数为 $99$​​，如果还有一份分数为 $10$​​ 的资料，那么他能获得的分数为 $109$​​，即最大上限。然后再从 $109$​​~$100$​ 所需要的最少天数转移到 $100$。这样就获得了第 $i$ 组分数为 $j$ 所需要的最少天数了。定义状态转移方程：
$$dp2[i][dp1[i][k]]=max(dp2[i][dp1[i][k]],k)dp1[i][k]<=500$$
为了到达分数 $k$​，至少需要 $k$ 天，也就是每天 $1$ 分，用刚刚的dp1转移到dp2，即到达分数 $k$ 所需天数如果小于 $k$ 的话，就更新。

接着枚举从一门课程开始预习复习，假设当前从课程 $i$ 开始，定义状态转移方程：
$$\begin{gathered} dp3[j][k]=dp3[j][k-1]k>0 \\ dp3[j][k]=max(dp3[j][k],dp3[j-l][k]+dp2[i][l])dp2[i][l]\ge 60 \\ dp3[j][k]=max(dp3[j][k],dp3[j-l][k-1]+dp2[i][l])k>0 \end{gathered}$$
前 $j$​​ 天，挂了 $k$​ 科所获得分一定从同样的天数，挂了 $k-1$​ 科转移而来。再挂科数相同都为 $k$​ 的情况下，枚举天数 $l$​，若前 $l$ 天获得得分数不小于 $60$，说明它可以从前 $j-l$ 天转移而来， 取最大值即可；如果小于 $60$，但 $k$ 不为 $0$，即还允许挂科，那么可以从前 $j-l$ 天，挂 $k-1$ 门科转移而来。而最后答案就是dp3[i][j]的最大值。

参考代码：

//参考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; //似乎只能为 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;
}

以上是std的做法，我太弱小了，有几串代码没看懂。然后去请教大佬，感觉下面代码容易理解些……

#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;
}