线性dp之过河问题
陈子骏
2018-04-01 16:54:02
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
int n,t[100001],opt[100001];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&t[i]);
sort(t+1,t+n+1);
opt[1]=0;
opt[2]=t[2];
for(int i=3;i<=n;i++)
opt[i]=min(opt[i-1]+t[1]+t[i],opt[i-2]+t[1]+t[i]+2*t[2]);
printf("%d",opt[n]);
}
```