```
#include <bits/stdc++.h>
using namespace std;
int n, s[1000007], f[1000007];
int Time(int n){
if(n == 1) return s[1];
else if(n == 2) return s[2];
else if(n == 3) return s[1] + s[2] + s[3];
else{
int T1 = s[n] + s[n-1] + 2 * s[1];
int T2 = 2 * s[2] + s[1] + s[n];
return min(T1, T2) + Time(n - 2);
}
}
int main(){
// 当n=1,2,3时,答案显而易见
// 当n=4时,有两种策略 :
// 1 :最快的依次送所有人
// 2 :最快的和次快的先过河,最快的回来,两个最慢的过河,次快的把船开回来
// 当 n != 4时, 则每次送走最慢的两个, 使用当前最优方案,直到 n < 4
scanf("%d", &n);
for(int i=1;i<=n;i++) scanf("%d", &s[i]);
sort(s+1,s+n+1);
printf("%d\n", Time(n));
return 0;
}
by XAKXIANGAKIOI @ 2020-09-10 21:21:37
这是AC代码,我一开始写的是用ans的,然后过不了,想知道有什么区别
by XAKXIANGAKIOI @ 2020-09-10 21:22:32
@[XAKXIANGAKIOI](/user/257635) 每次ans都会加上一个值啊
by asasas @ 2020-09-10 21:43:26
@[asasas](/user/261417)
大佬宁能说的详细一点吗
我智商比较低
by XAKXIANGAKIOI @ 2020-09-11 18:56:06
@[XAKXIANGAKIOI](/user/257635) 可能就是递归时ans的值不对
by asasas @ 2020-09-11 19:11:41
@[asasas](/user/261417)
大佬您能说一下为什么ans的值不对吗
by XAKXIANGAKIOI @ 2020-09-12 14:31:14
@[XAKXIANGAKIOI](/user/257635) 。。。您可以去调试一下,每次输出Ans
by asasas @ 2020-09-12 15:35:27
@[XAKXIANGAKIOI](/user/257635) 总之,这样写不太好
by asasas @ 2020-09-12 15:36:36