UVA607 Scheduling Lectures

换行出错。WA了一次。。

用a[i][j]表示从第i个主题上到第j个主题所需要的时间，d[i][0]表示上完第i个主题所需课时数的最小值，d[i][1]表示在上完第i个主题所需课时数最小的情况下，不满意度DI的最小值。

下面贴代码：

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 int a[1001][1001],d[1001][2],C,time;
 4 int DI(int a)
 5 {
 6     if(a == time)
 7         return 0;
 8     if(time - a <= 10)
 9         return -C;
10     return (time - a - 10) * (time - a - 10);
11 }
12 int main()
13 {
14     int ntopics;
15     int ncase = 0;
16     while(scanf("%d",&ntopics) == 1)
17     {
18         if(ntopics == 0)
19             break;
20         scanf("%d",&time);
21         scanf("%d",&C);
22         int i,j,k,temp;
23         //处理a[][]数组
24         a[0][0] = 0;
25         for(i = 1;i <= ntopics;i++)
26         {
27             scanf("%d",&temp);
28             k = i;
29             a[i - 1][i] = temp;
30             for(j = i - 2;j >= 0;j--)
31             {
32                 a[j][k] = temp + a[j][k - 1];
33             }
34         }
35         /*for(i = 1;i <= ntopics;i++)
36         {
37             for(j = 0;j < i;j++)
38                 printf("%d  ",a[j][i]);
39             printf("\n");
40         }*/
41         
42         //DP
43         d[0][0] = 0;
44         d[0][1] = 0;
45         for(i = 1;i <= ntopics;i++)
46         {
47             int temp1,temp2;
48             temp1 = temp2 = 0xffffff;
49             for(k = 0;k <= i - 1;k++)
50             {
51                 if(a[k][i] <= time && d[k][0] + 1 <= temp1)
52                 {
53                     temp1 = d[k][0] + 1;
54                     if(d[k][1] + DI(a[k][i]) < temp2)
55                         temp2 = d[k][1] + DI(a[k][i]);
56                 }
57             }
58             d[i][0] = temp1;
59             d[i][1] = temp2;
60         }
61         if(ncase)
62             printf("\n");
63         printf("Case %d:\n",++ncase);
64         printf("Minimum number of lectures: %d\n",d[ntopics][0]);
65         printf("Total dissatisfaction index: %d\n",d[ntopics][1]);
66     }
67     return 0;
68 }