UVa 607 - Scheduling Lectures

链接

传送门

题意

给出$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;
}

支付宝扫码领红包