zoj 3627 Treasure Hunt II （贪心）

本文出自 http://blog.csdn.net/shuangde800

题目链接： zoj-3627

题意

直线上有n个城市, 第i个城市和i+1个城市是相邻的. 每个城市都有vi的金币.
Alice和Bob站在城市p, 他们每天可以选择走向一个相邻的城市, 也可以选择不走. 他们是单独行动的.
他们经过一个城市就可以获得相应的金币(不能重复获得)
作为一个队伍, 他们的最远距离不能操作M, 问T天内, 他们最多一共能拿多少金币?

思路

由于每次只能走一步，那么一定是一个人往左走，一个人往右走，因为如果两个人一起往同一个方向走，
那么就和一个人一起走的效果是一样的。
这里题目还有一个限制：两个人的相差距离不能超过m，那么，就可以让两个人先走到相距m米处，然后
两个人同时一起往左边走，或者同时一起往右边走，这样就能保证两人的距离一直保持在m米内，又保证
尽量获取更大长度区间的金币。
所以，枚举两个人最开始走到相距m处的左右两点位置，然后再看剩下的时间还可以再继续一起往左或者
往右继续走多远，最终取最大值的情况即可。
需要注意边界的处理.

代码

<script src="https://code.csdn.net/snippets/716.js" type="text/javascript"></script>