poj1700

这题的最坑的地方就是每步可能会有两种情况，这两情况起初我都单独考虑了，但就是没放在一起考虑。。。wa个不停，果然贪心是一个很考验思维的东西。

这里可以这样考虑，在运人的过程中，河的起始岸最后终将剩下一个或者两个 人，并且是用时最大的。所以这个时候就会有两种情况，dp[i]=dp[i-1]+time[i]+time[0]

或者dp[i]=dp[i-1]+time[i]+time[0]+2*time[1];可见这类似于递归的思想。

#include"iostream"
#include"algorithm"
const int mx=10005;
int time[mx];
int dp[mx];//记录每步的最少时间
using namespace std;
int main()
{
    int t,i,j,n;
    cin>>t;
    while(t--)
    {
       cin>>n;
       for(i=0;i<n;i++)
        cin>>time[i];
       sort(time,time+n);
       dp[0]=time[0];
       dp[1]=time[1];
       for(i=2;i<n;i++)
       {
           int min1=dp[i-1]+time[i]+time[0];
           int min2=dp[i-2]+time[i]+time[0]+2*time[1];
           dp[i]=min1<min2?min1:min2;
       }
       cout<<dp[n-1]<<endl;
    }
    return  0;
}