题目背景
话说小 x 有一次去参加比赛, 虽然学校离比赛地点不太远, 但小 x 还是想坐 出租车去. 大学城的出租车总是比较另类, 有 "拼车" 一说, 也就是说, 你一个人 坐车去, 还是一堆人一起, 总共需要支付的钱是一样的 (每辆出租上除司机外最 多坐下 4 个人). 刚好那天同校的一群 Oier 在校门口扎堆了, 大家果断决定拼车 去赛场.
问题来了, 一辆又一辆的出租车经过, 但里面要么坐满了乘客, 要么只剩下 一两个座位, 众 Oier 都觉得坐上去太亏了, 小 x 也是这么想的.
题目描述
假设 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".
输入输出样例
输入样例 #1: 复制 2 2 10 5 1 1 2 2
输出样例 #1: 复制
14
这个是一个 dp, 对于 dp 数组的定义十分重要, 开始我定义前, 到第 i 分钟的时候还有 j 人没有上车, 我觉得我定义的一塌糊涂, 根本就不对, 感觉没有用脑袋思考, 后来看了题解之后
就知道最好定义成前 i 两个上了 j 个人花费的钱.
之前我自己的定义我觉得我是没有认真在写的, 因为题目中给了两个很明确的量, 一个是车辆一个是人数, 所以最好用这个来定义, 开始最好从正方向去定义, 因为我们一般对于
正方向比较熟练.
在这个定义完之后, 还有一个转移方程要写, 这个转移方程要注意不能直接去转移所有可能上去人数的, 因为两个车直接时间隔的太长了, 然后又不能一次性全部上车, 还不如之前可以上去,
就先上去了.
所以这个位置, 转移要注意, 可以有三层循环, 最内层就是对于每次上车多少人进行转移.
然后还有就是每一个 dp 因为要对自己进行转移, 所以就要给她赋初值. 这个初值不能乱赋, 而是赋值成如果不上这辆车的话, j 个人所用的费用.
- #include <stdio.h>
- #include <string.h>
- #include <algorithm>
- #include <iostream>
- #define inf 0x3f3f3f3f
- using namespace std;
- const int maxn = 110;
- int dp[maxn][maxn];
- struct node
- {
- int t, z;
- }exa[maxn];
- int main()
- {
- int n, d, k, s;
- cin>> n>> k>> d>> s;
- for (int i = 1; i <= k; i++) scanf("%d%d", &exa[i].t, &exa[i].z);
- for (int i = 1; i <= n; i++) dp[0][i] = inf;
- dp[0][0] = 0;
- for (int i = 1; i <= k; i++)
- {
- for (int j = 0; j <= n; j++)
- {
- dp[i][j] = dp[i-1][j];
- for (int k = 1; k <= min(j, exa[i].z); k++)
- {
- dp[i][j] = min(dp[i - 1][j - k] + k * exa[i].t + d, dp[i][j]);
- }
- }
- }
- if (dp[k][n]>= inf) printf("impossible\n");
- else printf("%d\n", dp[k][n]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2983913.html