信奧賽CSP-J復賽集訓（DP專題）（24）：P1977 出租車拼車

題目背景

話說小 x 有一次去參加比賽，雖然學校離比賽地點不太遠，但小 x 還是想坐出租車去。大學城的出租車總是比較另類，有“拼車”一說，也就是說，你一個人坐車去，還是一堆人一起，總共需要支付的錢是一樣的（每輛出租上除司機外最多坐下 $4$ 個人）。剛好那天同校的一群 OIer 在校門口扎堆了，大家果斷決定拼車去賽場。

問題來了，一輛又一輛的出租車經過，但里面要么坐滿了乘客，要么只剩下一兩個座位，眾 OIer 都覺得坐上去太虧了，小 x 也是這么想的。

題目描述

假設 $N$ 位 OIer 準備拼車，此時為 $0$ 時刻，從校門到目的地需要支付給出租車師傅 $D$ 元（按車次算，不管里面坐了多少 OIer），假如 $S$ 分鐘后恰能趕上比賽，那么 $S$ 分鐘后經過校門口的出租車自然可以忽略不計了。現在給出在這 $S$ 分鐘當中經過校門的所有的 $K$ 輛出租車先后到達校門口的時間 $T_i$ 及里面剩余的座位 $Z_i$
，OIer 可以選擇上車幾個人（不能超過），當然，也可以選擇上 $0$ 個人，那就是不坐這輛車。

俗話說，時間就是金錢，這里小 x 把每個 OIer 在校門等待出租車的分鐘數 等同于花了相同多的錢（例如小 x 等待了 $20$ 分鐘，那相當于他額外花了 $20$ 元錢）。

在保證所有 OIer 都能在比賽開始前到達比賽地點的情況下，聰明的你能計算出他們最少需要花多少元錢么？

輸入格式

每組數據以四個整數 $N$ , $K$ , $D$ , $S$ 開始，具體含義參見題目描述。

接著 $K$ 行，表示第 $i$ 輛出租車在第 $T_i$ 分鐘到達校門，其空余的座位數為 $Z_i$

時間按照先后順序。

輸出格式

對于每組測試數據，輸出占一行，如果他們所有人能在比賽前到達比賽地點，

則輸出一個整數，代表他們最少需要花的錢（單位：元），否則請輸出 impossible。

輸入輸出樣例 #1

輸入 #1

2 2 10 5
1 1
2 2

輸出 #1

14

說明/提示

對于 $100\%$ 的數據，滿足 $N,K,D,S\le 100$，$1\le Z_i\le 4$，$1\le T_i\le T_{i+1}\le S$。

AC代碼：

#include<bits/stdc++.h>
using namespace std;
/*思路： dp[i][j]:前i輛車坐了j個人的最小花費 狀態轉移方程：1、第i輛車不坐人: dp[i][j]=dp[i-1][j] 2、第i輛車坐m個人：1≤m≤min(z[i],j)dp[i][j]=min(dp[i-1][j-m]+m*a[i].t+d,dp[i][j])--ps1: dp[i-1][j-m]表示前i-1輛車坐了j-m個人的最小花費 --ps2：m*a[i].t+d：m個人坐第i輛車的等待時間花費+車費 
*/ 
int n,k,d,s,dp[110][110]; 
struct car{int t,z;
}a[110];
int main(){cin>>n>>k>>d>>s;for(int i=1;i<=k;i++){cin>>a[i].t>>a[i].z;}//dp初始化memset(dp,0x3f,sizeof(dp));dp[0][0]=0;//0個人0輛車的花費為0//遞推for(int i=1;i<=k;i++){//枚舉i輛車 for(int j=0;j<=n;j++){//枚舉j個人 dp[i][j]=dp[i-1][j];//如果第i輛車不坐人for(int m=1;m<=min(j,a[i].z);m++){//第i輛車坐m個人 dp[i][j]=min(dp[i-1][j-m]+m*a[i].t+d,dp[i][j]);}}} if(dp[k][n]==0x3f3f3f3f) cout<<"impossible";else cout<<dp[k][n]; return 0;
} 

文末彩蛋：

關注并查看老師的個人主頁，學習完整csp信奧賽完整系列課程： https://edu.csdn.net/lecturer/7901