J**B
发帖数: 204 | 1 有四个人要过一座桥，每次只能过两个人。P1 要1秒钟，p2 要2秒钟，p3要5秒钟，p4
要10秒钟，四个只有一个电筒，过桥的时候必需有一个人拿个电筒照明，请问最快多少
秒4个人可以全部通过。 | l*****a
发帖数: 14598 | 2 please check PIE
p4
【在 J**B 的大作中提到】
: 有四个人要过一座桥，每次只能过两个人。P1 要1秒钟，p2 要2秒钟，p3要5秒钟，p4
: 要10秒钟，四个只有一个电筒，过桥的时候必需有一个人拿个电筒照明，请问最快多少
: 秒4个人可以全部通过。
| c*********t
发帖数: 2921 | 3 这不就是DP吗？
【在 J**B 的大作中提到】
: 有四个人要过一座桥，每次只能过两个人。P1 要1秒钟，p2 要2秒钟，p3要5秒钟，p4
: 要10秒钟，四个只有一个电筒，过桥的时候必需有一个人拿个电筒照明，请问最快多少
: 秒4个人可以全部通过。
| J**B
发帖数: 204 | 4 啥 我不是CS出身，给稍微明确的hint吧。。。
【在 c*********t 的大作中提到】
: 这不就是DP吗？
| s******n
发帖数: 3946 | 5 1,2 ->
1 <-
5, 10 ->
2<-
1, 2-> | w****o
发帖数: 2260 | 6 大牛，
你能把这个formulate成一个DP吗？
谢谢！
【在 s******n 的大作中提到】
: 1,2 ->
: 1 <-
: 5, 10 ->
: 2<-
: 1, 2->
| J**B
发帖数: 204 | 7 能推荐点书么
1,2 -
★ Sent from iPhone App: iReader Mitbbs Lite 7.51
【在 s******n 的大作中提到】
: 1,2 ->
: 1 <-
: 5, 10 ->
: 2<-
: 1, 2->
| s******n
发帖数: 3946 | | S******t
发帖数: 151 | 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;i
scanf("%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;i
printf("%s",cross[i]);
return 0;
}
This version can handle n persons. |
|
