贪心/DP(动态规划)-UVA 10440-Ferry Loading II

「爱情、让人受尽委屈。」 2022-05-15 22:14 188阅读 0赞

# 贪心/DP(动态规划)-UVA 10440-Ferry Loading II #

--------------------

*  ## 题目链接：[10440 - Ferry Loading II][] ##
 *  ## 题目大意： ##

给定 **船一次性所能运的车数n**，**串往返(起点到终点或终点到起点）的时间t**，**车的总数m**及**每辆车到达起点的时间**，求**最少时间把车全部运过去的时间及运输次数**。

*  ## 解法一：贪心算法 ##

### 思路： ###

**要在最短时间把车全部运过去，因为船的往返时间固定，要运输时间最短就需要保证来回趟数最短，也就是尽可能满载运输**，这时有三种情况：

**a.Car\_Num<n：**如果车的数量比船一次性运载数小，直接等最后车来上船运到终点，**时间是最后车到达起点时间加上 t**

**b.Car\_Num>n：**

**①Car\_Num%n==0：**车数刚好是n的倍数，那么**让船每次满载后在开往终点**

**②Car\_Num%n!=0：先把多余的车Car\_Num%n运走，后面的满载**

**有一个小细节要考虑：车等船还是船等车** **Max(Car\_Ari\_Time\[Temp\_n\],Final\_Ari\_Time)****，取最大时间，如果船在起点车还没到，等车；车到起点船还没到，等船**

### 代码： ###

#include<iostream>
    using namespace std;
    
    #define MAX_Length 1445
    int Max(int a,int b)
    {
        return a>b? a : b;
    }
    
    int Car_Ari_Time[MAX_Length];
    
    int c,n,t,m;
    
    int main()
    {
        cin>>c;
        while(c--)
        {
            int Final_Ari_Time=0;
            int Carry_Time=0;
            cin>>n>>t>>m;
            for(int i=1;i<=m;i++)
                cin>>Car_Ari_Time[i];
            if(n>=m)
            {
                Carry_Time=1;
                Final_Ari_Time=Car_Ari_Time[m]+t;
            }
            else
            {
                if(m%n)     //first carry no-perfect num car
                {
                    int Left_Car=m%n;
                    Final_Ari_Time=Car_Ari_Time[Left_Car]+2*t;
                    int Temp_n=n;
                    Temp_n+=Left_Car;
                    while(Temp_n<=m)
                    {
                        Final_Ari_Time=Max(Car_Ari_Time[Temp_n],Final_Ari_Time);
                        Final_Ari_Time+=2*t;
                        Temp_n+=n;
                    }
                    Carry_Time=1+m/n;
                }
                else
                {
                    int Temp_n=n;
                    while(Temp_n<=m)
                    {
                        Final_Ari_Time=Max(Car_Ari_Time[Temp_n],Final_Ari_Time);
                        Final_Ari_Time+=2*t;
                        Temp_n+=n;
                    }
                    Carry_Time=m/n;
                }
    
                Final_Ari_Time-=t;     //haven arrived,do not return
            }
            cout<<Final_Ari_Time<<" "<<Carry_Time<<endl;
        }
        return 0;
    }

--------------------

## 解法二：DP(动态规划) ##

### 思路： ###

**让每辆车到达终点的时间都是最短的**，逐步优化直到最后一辆车。而且**在运输时间最短情况下运算次数是一定的**

**状态转移方程：DP\[i\]=min(DP\[i\] , max( DP\[j\]+t , Ari\_Time\[j\])+t)** ***DP\[i\]为第 i 辆车的到达时间，每次船都从终点出发***

**一样包括两种情况，车等船或船等车，max( DP\[j\]+t , Ari\_Time\[j\]) Ari\_Time\[j\]为第 j 辆车到达起点的时间**

**状态转移方程的比较范围：因为船具有最大运输量n，状态的选取具有一定的范围要求，必须是当前所要运载的车的*前n-1辆车*，很容易想，**一船最多载n车，所以最远可能运到 i 车的船趟不会在 n-1 外

//DP
    for (int j = MAX(0, i - n); j < i; j++)
    {
    	DP[i] = MIN(DP[i], MAX(DP[j] + t, Ari_Time[i]) + t);
    	Carry_Time[i] = MIN(Carry_Time[i], Carry_Time[j] + 1);
    }

### 代码： ###

#include<iostream>
    using namespace std;
    #define	Initial 1450
    int MAX(int a, int b)
    {
    	return a > b ? a : b;
    }
    int MIN(int a, int b)
    {
    	return a < b ? a : b;
    }
    
    int Carry_Time[Initial];
    int DP[Initial];
    int Ari_Time[Initial];  //运输次数
    int n, t, m;
    
    int main()
    {
    	int c;
    	cin >> c;
    	while (c--)
    	{
    		cin >> n >> t >> m;
    		for (int i = 1; i <= m; i++)
    			cin >> Ari_Time[i];
    		for (int i = 1; i <= m; i++)
    			DP[i] = Carry_Time[i] = 1e9;  //初始化为相对大的数
    
    		DP[0] = -t;     //每次船从终点出发
    		DP[1] = Ari_Time[1] + t;  //第一辆车唯有一种可能
    		Carry_Time[1] = 1;
    		for (int i = 2; i <= m; i++)
    		{
    			for (int j = MAX(0, i - n); j < i; j++)
    			{
    				DP[i] = MIN(DP[i], MAX(DP[j] + t, Ari_Time[i]) + t);
    				Carry_Time[i] = MIN(Carry_Time[i], Carry_Time[j] + 1);
    			}
    		}
    		cout << DP[m] << " " << Carry_Time[m] << endl;
    	}
    	return 0;
    }

[10440 - Ferry Loading II]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1381