首页 > 代码库 > 【POJ1700】Crossing River 贪心,附贪心问题的一系列详细解析
【POJ1700】Crossing River 贪心,附贪心问题的一系列详细解析
题意:一群人过河,船每次只能装两人,每次过河时间为两人权值较大的那个。
题解:
这种题的贪心策略往往不是很好想,这个时候我们就需要依照尽量逼近正解的思路,进行多种贪心,在每种贪心都保证正确的前提下,取多个答案的最值,这样往往就是正解,而即便可以卡,数据也很难出,并不是写个rand+debug拍上两个小时就能拍出来的。
而这种 多线程贪心 可以有两种:
一、单独做每种,然后取最优。
二、每一步转移都用多种贪心取得,然后直接取最后的状态值。
显然后一种的正确性比较高,但是往往因为“贪心”的奇葩性,而并不能写出这样的贪心。
而本题恰好可以用后一种贪心。
另外要说一下,就是这道题的贪心的方向有二:
一、每次过河的时间尽量小
二、过河的次数尽量少。
这样就又满足了一个性质,就是影响答案的几种条件都可以有针对策略时,我们将它们都进行选择,然后再加一些在几种条件之间进行妥协的策略,即牺牲某条件,迎合另一个条件的一系列策略。这样基本就是,或者说就已经是绝对正确的代码了。
而本题的两种策略则是
一、耗时最短的人一直在船上来回送人
二、耗时最短的来回送船,然后俩耗时最长的一起走。(实现:最短送船回来,俩人过去,次短来接最短过岸)
好了,贴代码:
#include <cstdio> #include <cstring> #include <algorithm> #define N 1005 using namespace std; int a[N],f[N],n; int main() { // freopen("test.in","r",stdin); int i,g; int ta,tb; scanf("%d",&g); while(g--) { scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&a[i]); sort(a+1,a+n+1); f[1]=a[1],f[2]=a[2]; for(i=3;i<=n;i++) { ta=f[i-1]+a[i]+a[1]; tb=f[i-2]+a[1]+a[2]+a[i]+a[2]; f[i]=min(ta,tb); } printf("%d\n",f[n]); } return 0; }
【POJ1700】Crossing River 贪心,附贪心问题的一系列详细解析
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。