首页 > 代码库 > 湘潭大学oj 1206 Dormitory's Elevator dp
湘潭大学oj 1206 Dormitory's Elevator dp
| 27153 | njczy2010 | 1206 | Accepted | 1976 KB | 234 MS | G++ | 1415 B | 2014-09-28 10:01:23 |
真是吐血ac，，，，这么easy的题。。。。。
Dormitory‘s Elevator | ||
| Accepted : 46 | Submit : 302 | |
| Time Limit : 1000 MS | Memory Limit : 65536 KB | |
Problem DescriptionThe 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. InputFirst 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. OutputOutput case number first, then the answer, the minimum of the total cost of student‘s walking cost. Sample Input13 2 1 12 3 Sample OutputCase 1: 1 Sourcedaizhenyang |
a代表上楼？？？？？？ 这点还是没弄清，，，，什么情况。。。。
好吧，，，，我懂了。。。。泪流满面啊。。。。
题解转自：http://blog.csdn.net/y990041769/article/details/39343269
分析：这其实就是一个简单的一维dp，用dp【i】表示从1层上到第 i 层花费的最小的体力。
因为不能在相邻的楼层停留，所以可以从dp【i-2】转移，但这样不是最优的还要从dp【i-3】转移，因为这样的话就可以到达所有的楼层。我们只要在所有的之间dp最优即可。
其他要注意的一个条件是，从dp【i-3】转移时，中间两层的人有四种选择：
1：都上去或都下来
2：上面的上去一层，下面的下来一层
3：上面的下来两层，下面的上去两层，（当时没有考虑到这个，要细心啊）
那么代码就很好写了、
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 #include<string>10 11 #define N 10000512 #define M 1513 #define mod 1000000714 //#define p 1000000715 #define mod2 10000000016 #define ll long long17 #define LL long long18 #define maxi(a,b) (a)>(b)? (a) : (b)19 #define mini(a,b) (a)<(b)? (a) : (b)20 21 using namespace std;22 23 int T;24 int n,m;25 int cnt[N];26 int a,b;27 int dp[N];28 int x;29 int ans;30 int c;31 32 void ini()33 {34 ans=0;35 memset(cnt,0,sizeof(cnt));36 memset(dp,0x3f3f3f3f,sizeof(dp));37 scanf("%d%d%d%d",&n,&m,&b,&a);38 c=min(a,b);39 for(int i=1;i<=m;i++){40 scanf("%d",&x);41 cnt[x]++;42 }43 dp[0]=0;44 dp[1]=0;45 dp[2]=0;46 dp[3]=c*cnt[2];47 48 }49 50 51 void solve()52 {53 int i;54 for(i=4;i<=n;i++){55 dp[i]=min(dp[i-2]+c*cnt[i-1],dp[i-3]+cnt[i-2]*min(a,2*b)+cnt[i-1]*min(b,2*a));56 }57 ans=min(dp[n],dp[n-1]+cnt[n]*a);58 }59 60 void out()61 {62 printf("%d\n",ans);63 }64 65 int main()66 {67 //freopen("data.in","r",stdin);68 //freopen("data.out","w",stdout);69 scanf("%d",&T);70 for(int ccnt=1;ccnt<=T;ccnt++)71 // while(T--)72 // while(scanf("%d%d",&n,&m)!=EOF)73 {74 // if(n==0 && m==0) break;75 printf("Case %d: ",ccnt);76 ini();77 solve();78 out();79 }80 81 return 0;82 }
湘潭大学oj 1206 Dormitory's Elevator dp