zoj 3627 F – Treasure Hunt II(贪心)

 
 
 

Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu

Submit Status

Description

There are n cities(12, … ,n) forming a line on the wonderland. city i and city i+1 are adjacent and their distance is 1. Each city has many gold coins. Now, Alice and her friend Bob make a team to go treasure hunting. They starts at city p, and they want to get as many gold coins as possible in T days. Each day Alice and Bob can move to adjacent city or just stay at the place, and their action is independent. While as a team, their max distance can’t exceed M.

Input

The input contains multiple cases.
The first line of each case are two integers np as above.
The following line contain n interger,”v1v2 … vn” indicate the gold coins in city i.
The next line is M, T.
(1<=n<=1000001<=p<=n0<=vi<=1000000<=M<=1000000<=T<=100000)

Output

Output the how many gold coins they can collect at most.

Sample Input

Sample Output

Hint

At day 1: Alice move to city 2, Bob move to city 4.

They can always get the gold coins of the starting city, even if T=0

 

 

贪心题。。一开始先尽量往两边走。。。走到最大距离M…

如果M是奇数的话还要考虑最后一步是谁走(因为最后一步只能一个人走,两个人走就超过M了)

然后分配剩下的时间。。如果往作走了i时间,那么往右就只能走t-2*i(因为还要回来)

然后取所有状态的最大值就好了。。。。

 

具体见代码注释。。。

 

View Code

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz