Hdu 4526 威威貓系列故事——拼車記

DP題。

dp[i][j]表示前i輛車送走j個人的最小花費。

狀態轉移方程是: dp[i][j] = min(dp[i][j],dp[i-1][j-p] + p*t[i] + d),其中0<=p<=z[i]。p代表第i輛車送走p個人。

細節部分和邊界條件看代碼。

[cpp]
#include <iostream>  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <math.h>  
#include <algorithm>  
#include <stack>  
#include <queue>  
using namespace std; 
 
int t[105]; 
int z[105]; 
//dp[i][j]表示前i輛車送走j個人的最小花費  
int dp[105][105]; 
 
int main() 
{ 
#ifndef ONLINE_JUDGE  
    freopen("in.txt","r",stdin); 
#endif  
    int cas; 
    scanf(" %d",&cas); 
    while(cas--) 
    { 
        memset(dp,0x3f3f3f3f,sizeof(dp)); 
        memset(t,0,sizeof(t)); 
        memset(z,0,sizeof(z)); 
 
        int n,k,d,s; 
        scanf(" %d %d %d %d",&n,&k,&d,&s); 
        dp[0][0] = 0;//注意0輛車0個人是0而不是inf  
        for(int i=1;i<=k;i++) 
        { 
            dp[i][0] = 0; 
            scanf(" %d %d",&t[i],&z[i]); 
        } 
        //第i輛車  
        for(int i=1;i<=k;i++) 
        { 
            //前i輛車一共送走j個人  
            for(int j=1;j<=n;j++) 
            { 
                //其中第i輛車送走p個人  
                for(int p=0;p<=z[i];p++) 
                { 
                    //前i-1輛車送走的人數  
                    int temp = (j>p) ? (j-p) : 0; 
                    int price = (p == 0) ? 0 : d; 
                    dp[i][j] = min(dp[i][j],dp[i-1][temp] + p*t[i] + price); 
                } 
            } 
        } 
        if(dp[k][n] == 0x3f3f3f3f) 
        { 
            printf("impossible\n"); 
        } 
        else 
        { 
            printf("%d\n",dp[k][n]); 
        } 
    } 
    return 0; 
}