暑假集训系列题解（三）
暑假集训系列题解（三）¶
题目1¶
题目链接¶
题目描述¶
Student Z doesn't love exams
The exam was about to be done soon, but student Z didn't even read the book, He had collapsed.
Student Z has a total of n exams, and there are still t days before the start of the exam, which means he still has t days to PREVIEW.
But student Z couldn’t even read the textbooks, and couldn’t review it at all. Fortunately, a kind classmate gave him m sets of review materials. The i set of materials can improve the grades of the si course. The i set of materials needs to be studied for yi days. You can increase xi points later (the upper limit of each course is 100 points, so after it is upgraded to 100 points, there will be no further increase).and note that each set of review materials can only be used once.
Student Z now has a zero-point level in every course. it is impossible to review all the materials, so he needs to choose some materials to review, but he can fail at most p courses in this semester (if the score of one course is less than 60 points will fail), otherwise he will be talked to by the professor.
Student Z now wants to know the maximum points he can get in all courses under the premise of fail no more than p courses this semester. If he cannot meet the conditions, please output −1 .
输入¶
A positive integer T (T≤10) in the first line represents the number of test cases.
For each test case:
The first line contains a positive integer n (n≤50) represents the total number of courses in this semester.
The second line contains n strings which length is no more than 15, representing the course name of each course in this semester.
The third line contains a positive integer m (m≤15000) represents the number of review materials he obtained.
In the next m lines, each line have a string s and two positive integers x(1≤x≤10) and y(1≤y≤10) , representing the course of this set of materials review, the improved scores and The number of days required for learning(data assurance this course was studied this semester ).
The last line has two integers t, p(1≤t≤500,0≤p≤3) represents the number of review days that student Z has and the upper limit of the number of failed courses in this semester.
输出¶
For each test case, output a line with a positive integer representing the maximum score that student Z can obtain in the case of meeting the conditions .If he must be talked to by the professor, output −1。
样例输入¶
1
3
mathematics physics signals
20
physics 10 1
physics 10 1
physics 10 1
physics 10 1
physics 10 1
physics 10 1
physics 10 1
mathematics 10 1
mathematics 10 1
mathematics 10 1
mathematics 10 1
mathematics 10 1
mathematics 10 1
mathematics 10 1
signals 10 1
signals 10 1
signals 10 1
signals 10 1
signals 10 1
signals 10 2
19 1
样例输出¶
题解¶
首先01背包求出每门课花费k天可以最多得到多少分，然后dp[i][k][l]前i门课程,复习了k天， 挂了l门课程的最大分数。
具体可参照博客：
https://blog.csdn.net/m0_46062697/article/details/119008022
代码¶
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
int mx[600] = {0};
int dp[60][600][60] = {0}; ///dp[i][j][k]代表学习前i门，用时j天。挂掉k门的最大分数
map<string, int> mp;
string str;
vector<pair<int, int>> v[60];
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
v[i].clear();
memset(dp, -0x3f, sizeof(dp));
mp.clear();
for (int i = 1; i <= n; i++)
{
cin >> str;
mp[str] = i;
}
int m, x, y;
scanf("%d", &m);
for (int i = 1; i <= m; i++)
{
cin >> str;
scanf("%d %d", &x, &y);
int index = mp[str];
v[index].push_back({x, y});
}
int t, p;
scanf("%d%d", &t, &p);
dp[0][0][0] = 0;
for (int i = 1; i <= n; i++)
{
memset(mx, -0x3f, sizeof(mx));
mx[0] = 0;
for (int j = 0; j < v[i].size(); j++)
for (int k = t; k >= v[i][j].second; k--)
mx[k] = max(mx[k], mx[k - v[i][j].second] + v[i][j].first);
for (int j = 0; j <= t; j++)
{
for (int k = j; k <= t; k++)
{
for (int l = 0; l <= p; l++)
{
if (mx[j] < 0)
continue;
int x = 0;
if (mx[j] < 60)
x = 1;
mx[j] = min(mx[j], 100);
if (l >= x)
dp[i][k][l] = max(dp[i][k][l], dp[i - 1][k - j][l - x] + mx[j]);
}
}
}
}
int ans = -0x3f;
for (int i = 0; i <= t; i++)
for (int j = 0; j <= p; j++)
ans = max(ans, dp[n][i][j]);
if (ans < 0)
puts("-1");
else
printf("%d\n", ans);
}
}