题目
传送门
题解
贪心、DP两种思路。
贪心
为了减少扣分，尽可能地按时完成扣分多的作业，按照这个思路自定义排序规则。按照扣分从多到少排序，然后每个作业的最后期限开始向第一天遍历占据时间完成作业，占据不到时间的即为无法完成。
DP
按照DP思路来考虑的话类似是一个01背包问题，把每个作业看作一件物品的话，物品的重量就是1，价值即为扣分，求解背包的最大容量，所有作业的扣分总和减去背包的最大容量即为解。按照作业完成最后期限从早到晚排序，避免晚完成的作业的状态无法向早完成的作业进行状态转移，状态转移公式为f[j] = max(f[j], f[j - 1] + h[i].score)，h[i].score为排序后第i份作业的扣分。
代码
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 1009;
int T, n;
struct Homework {
int ddl, score;
bool operator < (const Homework &a) const {
return ddl < a.ddl;
}
}h[N];
int f[N];
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &h[i].ddl);
}
int sumOfScore = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &h[i].score);
sumOfScore += h[i].score;
}
memset(f, 0, sizeof(f));
sort(h + 1, h + n + 1);
int sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = h[i].ddl; j >= 1; j--) {
f[j] = max(f[j], f[j - 1] + h[i].score);
sum = max(sum, f[j]);
}
}
printf("%d\n", sumOfScore - sum);
}
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 1009;
int T, n;
struct Homework {
int ddl, score;
bool operator < (const Homework &a) const {
return score > a.score;
}
}h[N];
bool f[N];
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &h[i].ddl);
}
for (int i = 1; i <= n; i++) {
scanf("%d", &h[i].score);
}
memset(f, 0, sizeof(f));
sort(h + 1, h + n + 1);
int sum = 0;
for (int i = 1; i <= n; i++) {
int t = h[i].ddl;
while(f[t]) t--;
if (t <= 0) {
sum += h[i].score;
} else {
f[t] = 1;
}
}
printf("%d\n", sum);
}
return 0;
}
|
