问个IQ 题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个IQ 题

问个IQ 题# JobHunting - 待字闺中

J*B2012-03-29 07:03

1 楼

有四个人要过一座桥，每次只能过两个人。P1 要1秒钟，p2 要2秒钟，p3要5秒钟，p4
要10秒钟，四个只有一个电筒，过桥的时候必需有一个人拿个电筒照明，请问最快多少
秒4个人可以全部通过。

l*a2012-03-29 07:03

2 楼

please check PIE

p4

【在 J**B 的大作中提到】

: 有四个人要过一座桥，每次只能过两个人。P1 要1秒钟，p2 要2秒钟，p3要5秒钟，p4
: 要10秒钟，四个只有一个电筒，过桥的时候必需有一个人拿个电筒照明，请问最快多少
: 秒4个人可以全部通过。

c*t2012-03-29 07:03

3 楼

这不就是DP吗？

【在 J**B 的大作中提到】

J*B2012-03-29 07:03

4 楼

啥我不是CS出身，给稍微明确的hint吧。。。

【在 c*********t 的大作中提到】

: 这不就是DP吗？

s*n2012-03-29 07:03

5 楼

1,2 ->
1 5, 10 ->
21, 2->

w*o2012-03-29 07:03

6 楼

大牛，
你能把这个formulate成一个DP吗？
谢谢！

【在 s******n 的大作中提到】

: 1,2 ->
: 1 : 5, 10 ->
: 2: 1, 2->

J*B2012-03-29 07:03

7 楼

能推荐点书么

1,2 -
★ Sent from iPhone App: iReader Mitbbs Lite 7.51

【在 s******n 的大作中提到】

: 1,2 ->
: 1 : 5, 10 ->
: 2: 1, 2->

s*n2012-03-29 07:03

8 楼

http://en.wikipedia.org/wiki/Bridge_and_torch_problem

S*t2012-03-29 07:03

9 楼

#include
#include
using namespace std;
char cross[3000][20];
int main()
{
int n,i,nc=0,sum=0,t[1000];
scanf("%d",&n);
for(i=0;iscanf("%d",&t[i]);
sort(t,t+n);
for(i=n-1;i>=3&&2*t[1]{
sprintf(cross[nc++],"%d %d\n",t[0],t[1]);
sprintf(cross[nc++],"%d\n",t[0]);
sprintf(cross[nc++],"%d %d\n",t[i-1],t[i]);
sprintf(cross[nc++],"%d\n",t[1]);
sum+=2*t[1]+t[0]+t[i];
}
for(;i>=2;i--)
{
sprintf(cross[nc++],"%d %d\n",t[0],t[i]);
sprintf(cross[nc++],"%d\n",t[0]);
sum+=t[0]+t[i];
}
if(i==1)
{
sprintf(cross[nc++],"%d %d\n",t[0],t[1]);
sum+=t[1];
}
else
{
sprintf(cross[nc++],"%d\n",t[0]);
sum+=t[0];
}
printf("%d\n",sum);
for(i=0;iprintf("%s",cross[i]);
return 0;
}
This version can handle n persons.