HDU - 4526 威威貓系列故事――拼車記 （DP）

HDU - 4526 威威貓系列故事――拼車記 （DP）

Description

　　話說威威貓有一次去參加比賽，雖然學校離比賽地點不太遠，但威威貓還是想坐出租車去。大學城的出租車總是比較另類，有“拼車”一說，也就是說，你一個人坐車去，還是一堆人一起，總共需要支付的錢是一樣的（每輛出租上除司機外最多坐下4個人）。剛好那天同校的一群Acmer在校門口扎堆了，大家果斷決定拼車去賽場。
　　問題來了，一輛又一輛的出租車經過，但裡面要麼坐滿了乘客，要麼只剩下一兩個座位，眾Acmer都覺得坐上去太虧了，威威貓也是這麼想的。
　　假設N名Acmer准備拼車，此時為0時刻，從校門到目的地需要支付給出租車師傅D元（按車次算，不管裡面坐了多少Acmer），假如S分鐘後恰能趕上比賽，那麼S分鐘後經過校門口的出租車自然可以忽略不計了。現在給出在這S分鐘當中經過校門的所有的K輛出租車先後到達校門口的時間Ti 及裡面剩余的座位Zi (1 <= Zi <= 4)，Acmer可以選擇上車幾個人（不能超過），當然，也可以選擇上0個人，那就是不坐這輛車。
　　俗話說，時間就是金錢，這裡威威貓把每個Acmer在校門等待出租車的分鐘數等同於花了相同多的錢（例如威威貓等待了20分鐘，那相當於他額外花了20元錢）。
　　在保證所有Acmer都能在比賽開始前到達比賽地點的情況下，聰明的你能計算出他們最少需要花多少元錢麼？

Input

輸入第一行為T，表示有T組測試數據。每組數據以四個整數N , K , D , S開始，具體含義參見題目描述，接著K行，表示第i輛出租車在第Ti分鐘到達校門，其空余的座位數為Zi（時間按照先後順序）。
[Technical Specification]
T <= 50
N <= 100
K <= 100
D <= 100
S <= 100
1 <= Zi <= 4
1<= T(i) <= T(i+1) <= S

Output

對於每組測試數據，輸出占一行，如果他們所有人能在比賽前到達比賽地點，則輸出一個整數，代表他們最少需要花的錢（單位：元），否則請輸出“impossible”。

Sample Input

 1
2 2 10 5
1 1
2 2 

Sample Output

 14 
思路：設dp[i][j]表示前i輛車還剩j個人的最小花費。那麼我們需要去每次枚舉減少的人
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 110;
const int inf = 0x3f3f3f3f;

int dp[maxn][maxn];
int n, k, s, d;

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%d%d", &n, &k, &d, &s);
		for (int i = 0; i <= k; i++)
			for (int j = 0; j <= n; j++)
				dp[i][j] = inf;

		dp[0][n] = 0;
		int last = 0;
		for (int i = 1; i <= k; i++) {
			int t, p;
			scanf("%d%d", &t, &p);
			for (int j = n; j >= 0; j--) {
				if (dp[i-1][j] != inf) {
					dp[i][j] = min(dp[i][j], dp[i-1][j] + j * (t - last));
					for (int l = 1; l <= p; l++)
						dp[i][j-l] = min(dp[i][j-l], dp[i-1][j] + j * (t - last) + d);
				}
			}
			last = t;
		}

		if (dp[k][0] == inf)
			printf("impossible\n");
		else printf("%d\n", dp[k][0]);
	}
	return 0;
}