链接
传送门
题意
给出\(n\)个主题，给出每节课的长度\(L\)和不满意度参数\(C\)，要安排课程。要求单个主题不能拆分在两节课上，主题间的顺序不能打乱。另外每堂课根据剩余时间\(x\)有不同不满意度：
- 当\(x = 0\)时，不满意度为0；
- 当\(1 \leq x \leq 10\)时，不满意度为\(-C\)；
- 当\(x \geq 11\)时，不满意度为\((x - 10) ^ 2\)。
输出最少安排课程的节数，和最小的不满意度。
思路
定义状态\(d[i][j]\)为上\(i\)节课，讲到第\(j\)个主题时最小的不满意度。对于\(d[i][j]\)如果第\(k\)个主题连续讲到第\(j\)个主题可以在一节课之内完成，则可以从\(dp[i - 1][k]\)转移。
代码
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
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 1010;
int a[maxn], L, C;
int dp[maxn][maxn];
inline int cal(int x) {
return x == 0 ? 0 : x > 10 ? (x - 10) * (x - 10) : C;
}
int main() {
int n, t = 0;
while (~scanf("%d", &n) && n) {
if (t) {
puts("");
}
scanf("%d%d", &L, &C);
C = -C;
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
a[i] += a[i - 1];
}
memset(dp, 0x3f, sizeof dp);
dp[0][0] = 0;
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; ++j) {
for (int k = j - 1; k >= i - 1; --k) {
int x = L - a[j] + a[k];
if (x >= 0) {
if (dp[i - 1][k] != inf) {
dp[i][j] = min(dp[i][j], dp[i - 1][k] + cal(x));
}
} else {
break;
}
}
}
if (dp[i][n] != inf) {
ans = i;
break;
}
}
printf("Case %d:\n", ++t);
printf("Minimum number of lectures: %d\n", ans);
printf("Total dissatisfaction index: %d\n", dp[ans][n]);
}
return 0;
}
|