程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ2336 Ferry Loading II 貪心動規

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;
//
//mapmp;
//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;
//
//mapmp;
//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;
}