XTUOJ 1206 Dormitory's Elevator
Dormitory's Elevator
| Time Limit : 1000 MS | ? | Memory Limit : 65536 KB |
Problem Description
The new dormitory has N(1≤N≤100000) floors and M(1≤M≤100000)students. In the new dormitory, in order to save student's time as well as encourage student exercise, the elevator in dormitory will not stop in adjacent floor. So if there are people want to get off the elevator in adjacent floor, one of them must walk one stair instead. Suppose a people go down 1 floor costs A energy, go up 1 floor costs B energy(1≤A,B≤100). Please arrange where the elevator stop to minimize the total cost of student's walking cost.All students and elevator are at floor 1 initially, and the elevator can not godown and can stop at floor 2.
Input
First line contain an integer T, there are T(1≤T≤10) cases. For each case T, there are two lines. First line: The number of floors N(1≤N≤100000), and the number of students M(1≤M≤100000),A,B(1≤A,B≤100) Second line: M integers (2≤A[i]≤N), the student's desire floor.
Output
Output case number first, then the answer, the minimum of the total cost of student's walking cost.
Sample Input
1 3 2 1 1 2 3Sample Output
Case 1: 1?
Source
daizhenyang
?
解題:動態規劃,同NYIST的詭異的電梯
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 100010; 4 int dp[maxn],des[maxn]; 5 int main(){ 6 int T,n,m,A,B; 7 scanf("%d",&T); 8 for(int t = 1; t <= T; ++t){ 9 memset(dp,0x3f,sizeof dp); 10 memset(des,0,sizeof des); 11 scanf("%d %d %d %d",&n,&m,&A,&B); 12 for(int i = 0,tmp; i < m; ++i){ 13 scanf("%d",&tmp); 14 des[tmp]++; 15 } 16 dp[1] = dp[2] = dp[0] = 0; 17 for(int i = 3; i <= n; ++i){ 18 dp[i] = dp[i-2] + min(A,B)*des[i-1]; 19 int x = min(B,A*2)*des[i-2]; 20 int y = min(B*2,A)*des[i-1]; 21 dp[i] = min(dp[i],dp[i-3] + x + y); 22 } 23 printf("Case %d: %d\n",t,dp[n]); 24 } 25 return 0; 26 } View Code?
轉載于:https://www.cnblogs.com/crackpotisback/p/4555479.html
總結
以上是生活随笔為你收集整理的XTUOJ 1206 Dormitory's Elevator的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 数据结构题目
- 下一篇: bzoj 3209 数位DP+欧拉定理