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