出租车拼车

题目

假设 N 位 Oier 准备拼车,此时为 0 时刻,从校门到目的地需要支付给出租

车师傅 D 元(按车次算,不管里面坐了多少 Oier),假如 S 分钟后恰能赶上比赛,

那么 S 分钟后经过校门口的出租车自然可以忽略不计了。现在给出在这 S 分钟当

中经过校门的所有的 K 辆出租车先后到达校门口的时间 T i 及里面剩余的座位 Zi

(1 <= Zi <= 4),Oier 可以选择上车几个人(不能超过),当然,也可以选择上 0 个

人,那就是不坐这辆车。

俗话说,时间就是金钱,这里小 x 把每个 Oier 在校门等待出租车的分钟数 等同于花了相同多的钱(例如小 x 等待了 20 分钟,那相当于他额外花了 20 元钱)。

在保证所有 Oier 都能在比赛开始前到达比赛地点的情况下,聪明的你能计 算出他们最少需要花多少元钱么?

输入输出格式

输入格式

每组数据以四个整数 N , K , D , S 开始,具体含义参见题目描述。

接着 K 行,表示第 i 辆出租车在第 Ti 分钟到达校门,其空余的座位数为 Zi

(时间按照先后顺序)。

N <= 100,K <= 100,D <= 100,S <= 100,1 <= Zi <= 4,1<= T(i) <= T(i+1) <= S

输出格式

对于每组测试数据,输出占一行,如果他们所有人能在比赛前到达比赛地点,

则输出一个整数,代表他们最少需要花的钱(单位:元),否则请输出“impossible”。

输入输出样例

输入样例

2 2 10 5

1 1

2 2

输出样例

14

思路

DP

用dp[i][j]表示前i辆车借走j个人需要花的钱

核心代码

F(i, 1, k) F(j, 0, n)
{
    dp[i][j] = dp[i-1][j];
    F(a, 1, Min(j, z[i]))
    {
        dp[i][j] = Min(dp[i][j], dp[i-1][j-a]+t[i]*a+d);
    }
}

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define LL long long
#define Max(x, y) (x >= y ? x : y)
#define Min(x, y) (x <= y ? x : y)
#define F(i, x, y) for(register int i=x; i<=y; i++)
#define R(i, x, y) for(register int i=x; i>=y; i--)
using namespace std;
inline void in(int &x)
{
static int ch; static bool flag;
for(flag=false, ch=getchar(); ch<'0'||ch>'9'; ch=getchar()) flag |= ch=='-';
for(x=0; isdigit(ch); ch=getchar()) x = (x<<1) + (x<<3) + ch - '0';
x = flag ? -x : x;
}
int n, k, d, s;
int t[105], z[105];
int dp[105][105];
inline int work()
{
memset(dp, 127/3, sizeof(dp));
int INF = dp[0][0];
in(n); in(k); in(d); in(s);
F(i, 1, k) in(t[i]), in(z[i]);
dp[0][0] = 0;
F(i, 1, k) F(j, 0, n)
{
dp[i][j] = dp[i-1][j];
F(a, 1, Min(j, z[i]))
{
dp[i][j] = Min(dp[i][j], dp[i-1][j-a]+t[i]*a+d);
}
}
if (dp[k][n] == INF) printf("impossible\n");
else printf("%d\n", dp[k][n]);
return 0;
}
int TAT = work();
int main() {;}