hdu 4526 拼車記 神奇的dp

威威貓系列故事——拼車記
Time Limit: 500/200 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 962    Accepted Submission(s): 293

Problem 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

Source
2013騰訊編程馬拉松初賽第五場（3月25日）
 

Recommend
liuyiding
 
思路：
 
dp[i][j]表示前i輛車送走j個acmer的最小花費，然後就有dp[i][j]=dp[i-1][j-k]+k*t+d;(t為車輛到達的時間，d為花費）,

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define mx 999999999
int dp[111][111];
int main()
{
    int i,j,k,cas,n,d,s;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d %d %d %d",&n,&k,&d,&s);
        for(i=0;i<=k;i++) for(j=0;j<=n;j++) dp[i][j]=mx;
        dp[0][0]=0;
        for(i=1;i<=k;i++)
        {
            int ti,num;
            for(j=0;j<=n;j++) dp[i][j]=dp[i-1][j];
            scanf("%d %d",&ti,&num);
            for(j=0;j<=n;j++)
            {
                for(int kk=0;kk<=num;kk++)
                    if(j>=kk)
                 dp[i][j]=min(dp[i][j],dp[i-1][j-kk]+ti*kk+d);
            }
        }
        if(dp[k][n]<mx)
             printf("%d\n",dp[k][n]);
        else
             puts("impossible");

    }
    return 0;
}