Problem B: Situp Benches
The gym at the University of Alberta has two identical sit up benches
that are side by side. Each of these benches can be inclined in 10
degree increments between 10 degrees and 50 degrees inclusive
depending on the level of difficulty the user desires. At the
end of each day the gym staff adjust the incline of each machine to be
10 degrees. This means at the start of each day both machines have a
10 degree incline.
Every time someone uses a bench it incurs some wear and tear that
amounts to 15 cents in maintenance costs. Additionally, every time a
bench has its incline changed it incurs wear and tear that amounts to
the number of degrees the bench was adjusted, in cents.
For example, if someone moves the bench from a 40 degree
incline to a 20 degree incline then 20 cents of maintenance must be
done.
The gym staff have recently required students to sign up for the situp
benches the day before. When a student signs up they give the time at
which they would like to use the machine and the incline they will use
it at. No more than two students can sign up to use a bench at the
same time.
Prior to opening the gym for the day, the gym staff would like to have
a list assigning students to each of the situp benches and they would
like the assignment to minimize the total maintenance cost for the
day. They have asked you to write a program to make this list.
Input begins with the number of test cases on its own line.
Each test case begins with the number n (1 ≤ n ≤ 10000), the
number of students who have signed up to use the benches on the
following day. Following are n lines, each consisting of two
numbers: time_slot and incline.
time_slot is a number that specifies when a student will arrive
at the machine, while incline specifies the angle to which they
will adjust the situp bench. Two students in the same time_slot arrive at the
benches at the same time, and lower time_slots occur before
higher time_slots. time_slots are numbered between 0 and 20000, and
incline is one of 10, 20, 30, 40 or 50 depending on the
student's preference.
For each test case, output a line containing the total maintenance cost (in cents) for the day
followed by n lines (one for each student, in the order given on input) containing
either a 1 or a 2 depending on which bench you have assigned them
to. Any assignment that minimizes the total maintenance cost for the
day is acceptable.
Sample Input
1
3
2 40
2 50
1 40
Sample Output
185
1
2
1
dp[time][第一台位置][第二台位置]去做轉移
#include <stdio.h>
#include <stdlib.h>
#define min(x,y) ((x)<(y)?(x):(y))
typedef struct {
int t, c, in;
} St;
int cmp(const void *i, const void *j) {
return ((St *)i)->t - ((St *)j)->t;
}
int cmp_out(const void *i, const void *j) {
return ((St *)i)->in - ((St *)j)->in;
}
int st[10005][6][6][5];
int main() {
int t, n, i, j, k;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
St D[10005];
for(i = 0; i < n; i++)
scanf("%d %d", &D[i].t, &D[i].c), D[i].c /= 10, D[i].in = i;
qsort(D, n, sizeof(St), cmp);
int dp[10005][6][6] = {}, ch = 0;
for(i = 1; i <= 5; i++)
for(j = 1; j <= 5; j++)
dp[0][i][j] = 0xfffffff;
dp[0][1][1] = 0;
for(i = 0; i < n; i++) {
ch++;
for(j = 1; j <= 5; j++)
for(k = 1; k <= 5; k++)
dp[ch][j][k] = 0xfffffff;
if(i+1 < n && D[i+1].t == D[i].t) {
st[ch][D[i].c][D[i+1].c][0] = 2;/*[0]cnt*/
st[ch][D[i+1].c][D[i].c][0] = 2;
for(j = 1; j <= 5; j++) {
for(k = 1; k <= 5; k++) {
if(dp[ch][D[i].c][D[i+1].c] > dp[ch-1][j][k]+abs(j-D[i].c)+abs(k-D[i+1].c)) {
dp[ch][D[i].c][D[i+1].c] = dp[ch-1][j][k]+abs(j-D[i].c)+abs(k-D[i+1].c);
st[ch][D[i].c][D[i+1].c][1] = j;/*state*/
st[ch][D[i].c][D[i+1].c][2] = k;
st[ch][D[i].c][D[i+1].c][3] = 1;/*choose*/
st[ch][D[i].c][D[i+1].c][4] = 2;
}
if(dp[ch][D[i+1].c][D[i].c] > dp[ch-1][j][k]+abs(k-D[i].c)+abs(j-D[i+1].c)) {
dp[ch][D[i+1].c][D[i].c] = dp[ch-1][j][k]+abs(k-D[i].c)+abs(j-D[i+1].c);
st[ch][D[i+1].c][D[i].c][1] = j;
st[ch][D[i+1].c][D[i].c][2] = k;
st[ch][D[i+1].c][D[i].c][3] = 2;
st[ch][D[i+1].c][D[i].c][4] = 1;
}
}
}
i++;
} else {
for(j = 1; j <= 5; j++) {
for(k = 1; k <= 5; k++) {
if(dp[ch][D[i].c][k] > dp[ch-1][j][k]+abs(j-D[i].c)) {
dp[ch][D[i].c][k] = dp[ch-1][j][k]+abs(j-D[i].c);
st[ch][D[i].c][k][0] = 1;
st[ch][D[i].c][k][1] = j;
st[ch][D[i].c][k][2] = k;
st[ch][D[i].c][k][3] = 1;
}
if(dp[ch][j][D[i].c] > dp[ch-1][j][k]+abs(k-D[i].c)) {
dp[ch][j][D[i].c] = dp[ch-1][j][k]+abs(k-D[i].c);
st[ch][j][D[i].c][0] = 1;
st[ch][j][D[i].c][1] = j;
st[ch][j][D[i].c][2] = k;
st[ch][j][D[i].c][3] = 2;
}
}
}
}
}
int ans = 0xfffffff;
for(i = 1; i <= 5; i++)
for(j = 1; j <= 5; j++)
ans = min(ans, dp[ch][i][j]+i+j-2);
int ti, tj;
for(i = 1; i <= 5; i++)
for(j = 1; j <= 5; j++)
if(ans == dp[ch][i][j]+i+j-2)
ti = i, tj = j;
int pel = n-1;
while(ch > 0) {
if(st[ch][ti][tj][0] == 1) {
D[pel].t = st[ch][ti][tj][3];
int tti = st[ch][ti][tj][1];
int ttj = st[ch][ti][tj][2];
ti = tti, tj = ttj;
pel--;
} else {
D[pel].t = st[ch][ti][tj][4];
D[pel-1].t = st[ch][ti][tj][3];
int tti = st[ch][ti][tj][1];
int ttj = st[ch][ti][tj][2];
ti = tti, tj = ttj;
pel -= 2;
}
ch--;
}
qsort(D, n, sizeof(St), cmp_out);
ans = ans*10 + n*15;
printf("%d\n", ans);
for(i = 0; i < n; i++)
printf("%d\n", D[i].t);
}
return 0;
}
文章定位: