过桥

过桥

思路

这道题可以用DP来做。
先把人按过去的时间从小到大排序，而且这个手电筒的传递都是有第一第二位来传（这样时间才最短）。
f[i]为前i个人过去所需的最短时间，那么方程就是 f [ i ] = m i n ( f [ i − 1 ] + a [ i ] + a [ 1 ] , f [ i − 2 ] + a [ 1 ] + a [ 2 ] + a [ 2 ] + a [ i ] ) ; f[i]=min(f[i-1]+a[i]+a[1],f[i-2]+a[1]+a[2]+a[2]+a[i]); f[i]=min(f[i−1]+a[i]+a[1],f[i−2]+a[1]+a[2]+a[2]+a[i]);
（左边是只要第一位传，右边是第一第二位一起传，用时间更短的那个方法传）

代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[1001],f[1001];
int main()
{scanf("%d",&n);//读入for (int i=1;i<=n;i++) scanf("%d",&a[i]);//读入sort(a+1,a+n+1);//排序（从小到大）f[1]=a[1];f[2]=a[2];//初始化for (int i=3;i<=n;i++)f[i]=min(f[i-1]+a[i]+a[1],f[i-2]+a[1]+a[2]+a[2]+a[i]);//动态转移方程printf("%d",f[n]);//输出return 0;
}

过桥

过桥

思路

这道题可以用DP来做。
先把人按过去的时间从小到大排序，而且这个手电筒的传递都是有第一第二位来传（这样时间才最短）。
f[i]为前i个人过去所需的最短时间，那么方程就是 f [ i ] = m i n ( f [ i − 1 ] + a [ i ] + a [ 1 ] , f [ i − 2 ] + a [ 1 ] + a [ 2 ] + a [ 2 ] + a [ i ] ) ; f[i]=min(f[i-1]+a[i]+a[1],f[i-2]+a[1]+a[2]+a[2]+a[i]); f[i]=min(f[i−1]+a[i]+a[1],f[i−2]+a[1]+a[2]+a[2]+a[i]);
（左边是只要第一位传，右边是第一第二位一起传，用时间更短的那个方法传）

代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[1001],f[1001];
int main()
{scanf("%d",&n);//读入for (int i=1;i<=n;i++) scanf("%d",&a[i]);//读入sort(a+1,a+n+1);//排序（从小到大）f[1]=a[1];f[2]=a[2];//初始化for (int i=3;i<=n;i++)f[i]=min(f[i-1]+a[i]+a[1],f[i-2]+a[1]+a[2]+a[2]+a[i]);//动态转移方程printf("%d",f[n]);//输出return 0;
}