ZJU1183-Scheduling Lectures

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int n;     //主题的数量
 5 int L, C;  //每节课的时间，常量C
 6 int *time; //每个主题需要的时间
 7 int *minLec; //主题1~i（1<=i<n)的最少讲课次数
 8 int *minDis; //与主题相应的最小不满意指标
 9 
10 //计算不满意指标
11 int DI(int t)
12 {
13     if (t == 0) return 0;
14     else if (t <= 10)return -C;
15     else return (t - 10)*(t - 10);
16 }
17 
18 
19 //动态规划的算法实现
20 void DP()
21 {
22     int i, j;
23     int cost;
24     int sum;
25     minDis[0] = 0;
26     minLec[0] = 0;
27     for (i = 1; i <= n; i++)
28     {
29         minLec[i] = 30000;
30         sum = 0;
31         for (j = i-1; j>=0; j--)
32         {
33             sum += time[j + 1];
34             if (sum > L) break;
35             if (minLec[j] + 1 > minLec[i]) continue;//如果j的次数+1大于i继续访问前面
36             cost = minDis[j] + DI(L - sum);
37             if (minLec[j] + 1 == minLec[i] && cost >= minDis[i]) continue;如果j的次数+1等于i，并且cost大于i的满意值，继续访问前面的
38             minDis[i] = cost;
39             minLec[i] = minLec[j] + 1;
40         }
41     }
42 }
43 
44 
45 void main()
46 {
47     cin >> n;
48     cin >> L >> C;
49     minDis = new int[n + 1];
50     minLec = new int[n + 1];
51     time = new int[n + 1];
52     for (int i = 1; i <= n; i++)
53         cin >> time[i];
54     DP();
55     cout << "Minimum number of lectures:" << minLec[n]<<endl;
56     cout << "Total dissatisfaction index:" << minDis[n] << endl;
57 }