Posted on 2008-04-17 23:14
superman 阅读(385)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
set opt[i][j] for the the min time of using i lessons cover the 1..j topics.
opt[i][j] = min{ opt[i - 1][j - k] + d(j - k + 1 .. j) }
1 /* Accepted 1183 C++ 00:01.91 4760K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int N;
9 cin >> N;
10 while(N--)
11 {
12 int n, l, c, t[1001], Case = 0,;
13 cin >> n;
14 while(n)
15 {
16 cin >> l >> c;
17 for(int i = 1; i <= n; i++)
18 cin >> t[i];
19
20 int d[1001][1001];
21 for(int i = 0; i <= n; i++)
22 for(int j = 0; j <= n; j++)
23 d[i][j] = INT_MAX;
24
25 d[0][0] = 0;
26
27 int i;
28 for(i = 0; i < n; i++)
29 {
30 if(d[i][n] != INT_MAX)
31 break;
32
33 for(int j = i; j < n; j++)
34 {
35 if(d[i][j] == INT_MAX)
36 break;
37
38 int x = l;
39 for(int k = j + 1; k <= n; k++)
40 {
41 x -= t[k];
42 if(x < 0)
43 break;
44
45 if(x == 0)
46 d[i + 1][k] <?= d[i][j];
47 else if(1 <= x && x <= 10)
48 d[i + 1][k] <?= d[i][j] - c;
49 else if(x > 10)
50 d[i + 1][k] <?= d[i][j] + (x - 10) * (x - 10);
51 }
52 }
53 }
54
55 cout << "Case " << ++ Case << ':' << endl << endl;
56 cout << "Minimum number of lectures: " << i << endl;
57 cout << "Total dissatisfaction index: " << d[i][n] << endl;
58
59 cin >> n;
60 if(n)
61 cout << endl;
62 }
63 if(N)
64 cout << endl;
65 }
66
67 return 0;
68 }
69