forked from AhmadElsagheer/UVa-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSchedulingLectures_UVa607.java
More file actions
115 lines (93 loc) · 2.34 KB
/
SchedulingLectures_UVa607.java
File metadata and controls
115 lines (93 loc) · 2.34 KB
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
package v006;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class SchedulingLectures_UVa607 {
static int N, L, C;
static int[] t;
static Pair[][] memo;
static Pair dp(int idx, int rem)
{
if(idx == N)
{
return new Pair(0, di(rem));
}
if(memo[idx][rem] != null) return memo[idx][rem];
Pair ans = new Pair(0, 0);
//open new lecture
Pair nxt = dp(idx + 1, L - t[idx]);
ans.lectures = nxt.lectures + 1;
ans.DI = nxt.DI + di(rem);
if(rem >= t[idx]) //compress
{
nxt = dp(idx + 1, rem - t[idx]);
if(nxt.lectures < ans.lectures)
{
ans.lectures = nxt.lectures;
ans.DI = nxt.DI;
}
else
if(nxt.lectures == ans.lectures)
ans.DI = Math.min(ans.DI, nxt.DI);
}
return memo[idx][rem] = ans;
}
static int di(int rem)
{
int di = 0;
if(rem >= 1 && rem <= 10)
di = -C;
else
if(rem > 10)
di = (rem - 10) * (rem -10);
return di;
}
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
int k = 1;
while(true)
{
N = sc.nextInt();
if(N == 0) break;
if(k != 1)
sb.append("\n");
sb.append("Case "+k++).append(":\n");
L = sc.nextInt();
C = sc.nextInt();
t = new int[N];
for(int i = 0; i < N; i++) t[i] = sc.nextInt();
memo = new Pair[N][L+1];
Pair ans = dp(0, 0);
sb.append("Minimum number of lectures: "+ans.lectures).append("\n");
sb.append("Total dissatisfaction index: "+ans.DI).append("\n");
}
System.out.print(sb);
}
static class Pair
{
int lectures, DI;
Pair(int x, int y)
{
lectures = x;
DI = y;
}
}
static class Scanner {
StringTokenizer st;
BufferedReader br;
public Scanner(InputStream s){ br = new BufferedReader(new InputStreamReader(s));}
public String next() throws IOException
{
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
}
public int nextInt() throws IOException {return Integer.parseInt(next());}
public long nextLong() throws IOException {return Long.parseLong(next());}
public String nextLine() throws IOException {return br.readLine();}
public boolean ready() throws IOException {return br.ready();}
}
}