此题讲的是N个人过河，每个人都有自己的过河时间，一条船只能承受2个人，所用时间为其中过河时间最多的，所以呢，想到有两种情况，第一种：过河时间最少的人来回接送其他人，第二种：过河时间最少和次少的人来回接送其他人，，刚开始就觉得第一种时间必然是最少的，但是仔细想想，不然。因为第一种情况虽然单次过河时间少，但送人的次数要多，如第1个人（过河时间最少）接送第i人dp[i]=dp[i-1]+time[0]+time[i]； 而第二种情况呢，虽然来回次数多，但是接送的人要多，如第1个人接第i-1个和第i个人，然后让第i-1个和第i个人一块过河，第2个人再接送第1个人。dp[i]=dp[i-2]+time[0]+time[i]+time[1]*2。所以每次计算出这两个值都应该进行比较，从而AC！//（转）
#include <iostream>#include <algorithm>using namespace std;int dp[1050];int cmp(int a, int b){return a<b;}int main (){ int t; cin>>t; while(t–) {int n;cin>>n;int a[1050];int i;for(i=0; i<n; i++)cin>>a[i];sort(a,a+n,cmp);dp[0]=a[0];dp[1]=a[1];for(i=2; i<n; i++){int min1=dp[i-1]+a[i]+a[0];int min2=dp[i-2]+a[i]+2*a[1]+a[0];if(min1>min2)dp[i]=min2;elsedp[i]=min1;}cout<<dp[n-1]<<endl; }// system("pause"); return 0;}
鸟的翅膀在空气里振动，那是一种喧嚣而凛裂的，
