【題目描述】

幾個人過河，每次過兩人一人回，速度由慢者決定，問過河所需最短時間。

【輸入】

輸入t組數據，每組數據第1行輸入n，第2行輸入n個數，表示每個人過河的時間。

【輸出】

輸出t行數據，每行1個數，表示每組過河最少時間。

【輸入樣例】

1
4
1 2 5 10

【輸出樣例】

17

【源程序】

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define INF 999999999 #define N 1001 using namespace std; int a[N],dp[N]; int main() {int t;int n;cin>>t;while(t--){cin>>n;for(int i=0;i<n;i++)cin>>a[i];sort(a,a+n);dp[0]=a[0];dp[1]=a[1];for(int i=2;i<n;i++)dp[i]=min(dp[i-1]+a[0]+a[i],dp[i-2]+a[0]+a[i]+a[1]*2);cout<<dp[n-1]<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的Crossing River（信息学奥赛一本通-T1232）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。