过河问题 这个题目是之前微软的面试题,很经典. 问题难点在于还要把船送回来. 特殊点是起始和最后的,要考虑把所有人送过去,有一点就是最快的人送回来的速度最快,但同时发现如果最慢的两个人过去,节约了一个最慢的时间,但是送回来的时间却很长,这样就要最快的提前过去. 注意正确状态是所有人都到了对岸. PS:
考虑当前最慢的人，如果要把它送过去 1.可以利用最快的和它一起过去，，最快的回来【用别的人显然没有这个优】 2.利用船的性质：两个人划船时间取决于最慢的人，那么这个最慢的人过去的时候还可以把次慢的人一起送过去，省的以后再管次慢的人，但这种方案是建立在对岸有个比较快的人能把船划回来的基础上【否则就变成第一种情况了】，我们当然希望划回来的人尽量快，所以应该是最快的在对岸把船划回来，要把最快的人留在对岸就要最快的和次快的一起过去，次快的回来。这样一来，最慢的和次慢的都去了对岸，最快的和次快的又都回到原地，缩小规模，状态不变
第二种方案建立在还有大于等于4个人的基础上，最后剩余的特别考虑即可
ll;;ll dp[maxn];int a[maxn],b[maxn];int main(){int T;scanf(“%d”,&T);while(T–){int n;scanf(“%d”,&n);for(int i = 0;i<n;i++)scanf(“%d”,a+i);sort(a,a+n);dp[0] = a[0];dp[1] = a[1];dp[2] = a[0] + a[1] + a[2];for(int i = 3;i<n;i++){dp[i] = min( a[0]+a[i]+a[1]+a[1], a[0]+a[0]+a[i]+a[i-1]) + dp[i-2] ;}printf(“%d\n”,dp[n-1]);}return 0;}
你在会议中吵架时，尼泊尔的背包客一起端起酒杯坐在火堆旁。
