Scheduling Lectures

You are teaching a course and must cover n ( ) topics. The length of each lecture is L ( ) minutes. The topics require ( ) minutes each. For each topic, you must decide in which lecture it should be covered. There are two scheduling restrictions:

1.

Each topic must be covered in a single lecture. It cannot be divided into two lectures. This reduces discontinuity between lectures.

2.

Topic i must be covered before topic i + 1 for all . Otherwise, students may not have the prerequisites to understand topic i + 1.

With the above restrictions, it is sometimes necessary to have free time at the end of a lecture. If the amount of free time is at most 10 minutes, the students will be happy to leave early. However, if the amount of free time is more, they would feel that their tuition fees are wasted. Therefore, we will model the dissatisfaction index (DI) of a lecture by the formula:

where C is a positive integer, and t is the amount of free time at the end of a lecture. The total dissatisfaction index is the sum of the DI for each lecture.

For this problem, you must find the minimum number of lectures that is needed to satisfy the above constraints. If there are multiple lecture schedules with the minimum number of lectures, also minimize the total dissatisfaction index.

Input 

The input consists of a number of cases. The first line of each case contains the integer n, or 0 if there are no more cases. The next line contains the integers L and C. These are followed by n integers .

Output 

For each case, print the case number, the minimum number of lectures used, and the total dissatisfaction index for the corresponding lecture schedule on three separate lines. Output a blank line between cases.

Sample Input 

6
30 15
10
10
10
10
10
10
10
120 10
80
80
10
50
30
20
40
30
120
100
0

Sample Output 

Case 1:
Minimum number of lectures: 2
Total dissatisfaction index: 0

Case 2:
Minimum number of lectures: 6
Total dissatisfaction index: 2700

---

Miguel A. Revilla
1999-04-06

題目描述：
每一堂課有 L 的時間, 然後要在課堂中講許多個主題(課題), 但是這些課題必須要依序講, 不可以跳過之前的課題先講, 但每個課題都有分別占有的時間, 而每堂課雖然有 L 分鐘, 但塞不滿會剩餘時間 t, 這個 t 時間會造成不滿意度的, 計算方式照題目所說, 要求在最少堂課中的最低不滿意度。

題目解法：
dp[i][j] 表示已經上了 i 堂, 也結束了 j 個課題, 那麼我們可以窮舉接下來這堂課要上多長。


#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int dp[1005][1005];
int main() {
    int n, L, C;
    int i, j, k;
    int cases = 0;
    int time[1005];
    while(scanf("%d", &n) == 1 && n) {
        scanf("%d %d", &L, &C);
        for(i = 1; i <= n; i++)
            scanf("%d", &time[i]);
        memset(dp, 63, sizeof(dp));
        const int oo = dp[0][0];
        int ret = oo;
        dp[0][0] = 0;
        if(cases)   puts("");
        printf("Case %d:\n", ++cases);
        for(i = 0; i <= n; i++) {
            if(dp[i][n] != oo) {
                printf("Minimum number of lectures: %d\n", i);
                printf("Total dissatisfaction index: %d\n", dp[i][n]);
                break;
            }
            for(j = 0; j < n; j++) {
                if(dp[i][j] == oo)  continue;
                int sum = 0;
                for(k = j+1; k <= n; k++) {
                    sum += time[k];
                    if(sum > L)
                        break;
                    if(L - sum == 0)
                        dp[i+1][k] = min(dp[i+1][k], dp[i][j]);
                    else if(L - sum <= 10)
                        dp[i+1][k] = min(dp[i+1][k], dp[i][j] - C);
                    else
                        dp[i+1][k] = min(dp[i+1][k], dp[i][j] + (L-sum-10)*(L-sum-10));

                }
            }
        }
    }
    return 0;
}