POJ2336 Ferry Loading II 贪心动规 - c++编程基础

题意：有m辆车，每次最多运n辆过河，过河过去需要t时间回来需要t时间，m辆车一开始并不是都在岸边的，给出m辆车抵达岸边的时间（只有车抵达河岸才能过河），问使得所有车辆过河所需要的最少次数跟最早时间

分析：

一开始看题目可能觉得有两个最优解，最少次数跟最早时间，次数最少猜测一下，m%n==0则刚好为m/n次否则为m/n+1次，然后考虑最早时间，时间要最早其实就是最后一辆车最早过河了即可，那么最后一辆车尽早被送走就好，看样子可以贪心

举了几个案例试了一下，若m%n==0则不用说了，每次运n辆车过河即可，这样既保证了次数最少又保证了时间最早

若m%n!=0，那么第一次运m%n辆车，剩下的每次运n辆车即可，所以贪心是可以的

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #define ll long long #define LL __int64 #define eps 1e-8 //const ll INF=9999999999999; #define inf 0xfffffff using namespace std; //vector
                
                  > G; //typedef pair
                 
                   P; //vector
                  
                   > ::iterator iter; // //map
                   
                    mp; //map
                    
                     ::iterator p; int n,t,m; int time[1000000]; void clear() { memset(time,0,sizeof(time)); } int main() { int Case; scanf("%d",&Case); while(Case--) { scanf("%d %d %d",&n,&t,&m); clear(); int r = m%n; int k = m/n; int ans1 = 0,ans2; if(r) ans2 = k + 1; else ans2 = k; for(int i=1;i<=m;i++) scanf("%d",&time[i]); if(r) ans1 = time[r] + t * 2; int j = 1; while(j <= k) { if(ans1 >= time[j * n + r]) { ans1 += t * 2; if(j == k) ans1 -= t; } else { ans1 = time[j * n + r] + t * 2; if(j == k) ans1 -= t; } j++; } printf("%d %d\n",ans1,ans2); } return 0; }

这道题贪心可以，那么深入试了一下，动规也是可以的，

dp[i]表示送走第i辆车的最早时间

num[i]表示送走第i辆车的次数

注意时间的早和晚不能直接取的，因为车子到了你才能运过河，

所以状态转移方程有个去当前dp数组值与当前的time数组值最大值的地方要注意

dp[i] = min(max(dp[j] + t,time[i]) + t),其中j为 i-n 到i

次数转移就简单了直接 num[i] = num[j] + 1，其中j为最小的

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #define ll long long #define LL __int64 #define eps 1e-8 //const ll INF=9999999999999; #define inf 0xfffffff using namespace std; //vector
                
                  > G; //typedef pair
                 
                   P; //vector
                  
                   > ::iterator iter; // //map
                   
                    mp; //map
                    
                     ::iterator p; int n,t,m; int time[10000]; int dp[10000]; int num[10000]; void clear() { memset(time,0,sizeof(time)); memset(dp,0,sizeof(dp)); memset(num,0,sizeof(num)); } int main() { int Case = 0; scanf("%d",&Case); while(Case--) { clear(); scanf("%d %d %d",&n,&t,&m); for(int i=1;i<=m;i++) scanf("%d",&time[i]); dp[0] = -t; dp[1] = time[1] + t; num[1] = 1; for(int i=2;i<=m;i++) { for(int j=max(0,i-n);j
                     
                       tmp) { dp[i] = tmp; num[i] = num[j] + 1; } } } printf("%d %d\n",dp[m],num[m]); } return 0; }