after crossing overhims...

来源：蜘蛛抓取(WebSpider) 时间：2011-10-09 16:55 标签： crossing over
1541人阅读
动态规划（46）
比赛题（80）
River Crossing
时间限制：&ms &|& 内存限制：65535&KB
Afandi is herding&N&sheep&across the expanses of&grassland&&when he finds himself blocked by a river. A single raft is available for transportation.
Afandi knows that he must ride on the raft for all crossings, but adding sheep to the raft makes it traverse the river more slowly.
When Afandi is on the raft alone, it can cross the river in M minutes When the i sheep are added, it takes Mi minutes longer to cross the river than with i-1 sheep (i.e., total M+M1 &&minutes with one sheep, M+M1+M2
with two, etc.).
Determine the minimum time it takes for Afandi to get all of the sheep across the river (including time returning to get more sheep).
On the first line of the input is a single positive integer k, telling the number of test cases to follow. 1 ≤ k ≤ 5 Each case contains:
* Line 1: one space-separated integers: N and M (1 ≤ N ≤ 1000 , 1≤ M ≤ 500).
* Lines 2..N+1: Line i+1 contains a single integer: Mi (1 ≤ Mi ≤ 1000)
For each test case, output a line with the minimum time it takes for Afandi to get all of the sheep across the river.
这是去年省赛的一道题，当时写的代码交上去一直WA，和队友讨论了好长时间也没找到哪里错了。后来才知道我们的思想就是错的。因为这个题是dp，但是我们一直当成贪心做的。比赛完就放下没做，没想到今天比赛又拉出来了，虽然知道是dp，但是由于没有找到状态转移方程，导致今天又没有做出来。好伤心。。。。
题意：有1个人和N只羊要过河。一个人单独过河花费的时间是M，每次带一只羊过河花费时间M+M1，带两只羊过河花费时间M+M1+M2……给出N、M和Mi，问N只羊全部过河最少花费的时间是多少。
分析：用一个前缀和数组time，time[i]表示单独运送i只羊所花费的时间。dp[i]表示一个人和i只羊过河所花费的最短时间，则开始时dp[i] = time[i] + M，以后更新时，dp[i] = min（dp[i]，dp[i-j] + m + dp[j]），j从1循环到i-1，即把i只羊分成两个阶段来运，只需求出这两个阶段的和，然后加上人从对岸回来所用的时间，与dp[i]进行比较，取最小值。
#include&stdio.h&
#include&algorithm&
int dp[1005], time[1005];
int main()
int T, n, m, i,
scanf(&%d&,&T);
while(T--)
scanf(&%d%d&,&n, &m);
time[0] = 0;
for(i = 1; i &= i++)
scanf(&%d&,&a);
time[i] = time[i-1] +
for(i = 1; i &= i++)
dp[i] = time[i] +
for(j = 1; j & j++)
dp[i] = min(dp[i], dp[i-j] + dp[j] + m);
printf(&%d\n&,dp[n]);
//time[i]表示一次运送i只羊所花费的时间
//dp[i]表示人和i只羊一起过河所花费的最短时间
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：431198次
积分：7499
积分：7499
排名：第2253名
原创：318篇
评论：74条
(2)(3)(3)(1)(3)(1)(1)(2)(12)(10)(17)(12)(35)(20)(1)(4)(31)(14)(16)(10)(1)(7)(6)(3)(9)(25)(5)(15)(30)(7)(1)(12)The Barbados advocate ( Friday, December 08, 1950 )

我要回帖

更多关于 crossing over 的文章

 

随机推荐