2011-12-30 07:50:18Morris
[PTC] Problem C Elevator
Problem C
Elevator
Input file: testdata.in
Time limit: 2 seconds
In a skyscraper people take elevators to go to their destination floors. How-Time limit: 2 seconds
Problem Description
ever if elevators are not well placed at the beginning, people will spend a
lot of time waiting for the elevators. If an elevator takes a unit of time to
move from one floor to the next floor, what is the minimum possible ex-
pected waiting time for all requests? Formally when we are given the height
of the skyscraper (H), the number of elevators (E), the initial placement of
E elevators, and the pro ability that requests come from each floor, how to
minimize the expected waiting time for all requests?
For example, we assume that there are two elevators in a skyscraper of
eleven floors, and the ratio among the probability that a request comes from
a particular floor is 10 : 1 : 1 : 1 : 1 : 1 : 1 : 1 : 1 : 1 : 1. Now if we place the
elevators on the first and the eighth floors, then in average a request will be
served in 9/10 unit of time. Let pi be the probability that a request comes from
floor i. In this example, p1 = 10/20 = 0.5 and all pi from all other floors will
be 1/20 = 0.05. We also assume that a request will be served by the nearest
elevator, so the request from the fifth to the eleventh floor will be severed by
the elevator at the eight floor, and the requests from the first the to fourth
floor will be severed by the elevator at the first floor. As the result in average
a request will be served in P1i4 |i − 1| × pi + P5i11 |i − 8| × pi = 9/10 .
Technical Specification
• 1 ≦H ≦1000
• 1 ≦E ≦ 20
• The probability ratio for request from each floor is represented by a
non-negative integer no greater than 5000.
Input FormatThere are several test cases (no more than 20). The first line of a test case
has two integers, H and E. The next line has H integers for the probability
ratio from the first to the N-th floor.
Output Format
For each test case output the minimum expected waiting time in simple
fraction form. If the denominator is 1 you only output the numerator.
Sample Input
11 2
10 1 1 1 1 1 1 1 1 1 1
11 2
1 0 0 0 0 0 0 0 0 0 1
6 3
0 0 0 0 0 0
3 6
9 9 9
Sample Output
9/10
0
0
0
題目意思 : 計算 E 台電梯在 H 樓層, 等待要求最小的期望值
作法 : DP
DP[i][k] //現在有 i 台電梯, 而最後一台電梯的位置 k
我們可以得到
DP[i+1][s] = min(DP[i][k] + 期望值) //s > k
期望值要重新算的部分為
k->(s+k/2) 分給位置在 k 的電梯
(s+k/2)->h 分給位置在 s 的電梯
#include<stdio.h>
long long gcd(long long x, long long y) {
long long tmp;
while(x%y) {
tmp = x, x = y, y = tmp % y;
}
return y;
}
long long ER[1001][1001], EL[1001][1001];
int main() {
int H, E, i, j, k, l, m;
int Ele[1001] = {0};
while(scanf("%d %d", &H, &E) == 2) {
long long sum = 0, cost;
long long DP[21][1001] = {0}, min;
for(i = 1; i <= H; i++)
scanf("%d", &Ele[i]), sum += Ele[i];
if(sum == 0 || E >= H) {puts("0");continue;}
for(i = 1; i <= H; i++) {
long long tmpsum = 0;
for(j = i; j <= H; j++) {
tmpsum += (j-i)*Ele[j];
ER[i][j] = tmpsum;
}
}
for(i = 1; i <= H; i++) {
long long tmpsum = 0;
for(j = i; j >= 1; j--) {
tmpsum += (i-j)*Ele[j];
EL[i][j] = tmpsum;
}
}
for(i = 1; i <= E; i++) { /*i台*/
for(j = 1; j <= H; j++) {/*j位置*/
min = 0xffffffff;
for(k = 0; k < j; k++) {/*i-1台 k 位置*/
if(i == 1 && k > 0) break;
if(i > 1 && k == 0) continue;
cost = DP[i-1][k];
if(i > 1) {
/* for(l = k; l <= H; l++)
cost -= abs(l-k)*Ele[l];*/
cost -= ER[k][H];
}
m = (k+j)/2;
if(i == 1) m = 0;
cost += ER[k][m];
cost += EL[j][m+1];
cost += ER[j][H];
/* for(l = k; l <= m; l++)
cost += abs(l-k)*Ele[l];
for(l = m+1; l <= H; l++)
cost += abs(l-j)*Ele[l];
*/
if(cost < min) min = cost;
}
DP[i][j] = min;
}
}
min = 0xffffffff;
for(i = 1; i <= H; i++)
if(min > DP[E][i])
min = DP[E][i];
long long x = min, y = sum, Gcd = gcd(x, y);
x /= Gcd, y /= Gcd;
if(y == 1)
printf("%lld\n", x);
else
printf("%lld/%lld\n", x, y);
}
return 0;
}