ICPC 2020沈阳站 - H. The Boomsday Project（dp，双指针优化）

100 阅读 0 评论 66 点赞

我是靠谱客的博主无私狗，这篇文章主要介绍ICPC 2020沈阳站 - H. The Boomsday Project（dp，双指针优化），现在分享给大家，希望可以做个参考。

https://codeforces.com/gym/103202/problem/H

题意
平常每次租用共享单车花费 $r$ 元。
给定 n 种折扣卡，每张折扣卡 $c_i$ 元，能够在包括购买当天的 $d_i$ 天内免费骑车 $k_i$ 次。
现在有 m 条使用记录，每条记录给出 $p_i$ 和 $q_i$ ，表示将会在第 $p_i$ 天租用单车 $q_i$ 次。
问，如何购买折扣卡能使得总花费最小，输出最小花费。

$10^5, 1 leq r leq 10^9$
$d_i, k_i, c_i leq 10^9$
$p_i leq 10^9, 0 leq q_i leq 3 times 10^5, sum_{i=1}^m q_i leq 3 times 10^5$

思路
注意到 q_i 的数据范围 $sum_{i=1}^m q_i leq 3 times 10^5$ ，可以把每天的 $q_i$ 次记录铺开，所有的使用记录构成一个数列，表示都在第几天用了，例如：2 2 3 3 3 4 5 5，这样就转化成了 $p_i*q_i$ 条记录。
转化之后就和今年蓝桥杯的一道 dp 题（费用报销）类似。

定义状态 f[i] 表示，前 i 条记录的最小花费。

对于当前这一天，遍历所有种类的卡片，从前面找条记录 x 使用当前卡片，能够使得从第 x 条记录开始到当前这条记录都不用花费，那么状态就可以由前 x-1 条记录的花费加上卡片的花费来转移。
因为状态定义的是前 i 条记录的最小花费，那么越靠前花费越小，所以每次找到最靠前的满足条件的位置来转移。
因为每种卡片免费的限制条件是使用次数和天数，而此时数组是按照时间排序的，所以对于每种卡片而言，随着遍历记录的后移，最靠前的满足条件的位置也单调往后走，所以可以用一个指针来指，每次遍历一条记录就往后走到转移位置，就省去了遍历转移位置的这一重遍历。

（一开始想在当前记录使用卡片，但是这样就会对后面产生贡献，当前这条记录的状态没办法转移，那么不妨在前面的某条记录使用，能对当前这条记录产生贡献，直接从其前一条记录的状态+卡片花费来转移就行了）

Code

复制代码

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
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 300010, mod = 1e9+7;
int T, n, m;
int r;
struct node{
	int day, cnt, price;
}a[N];
int b[N];
int pos[N];
int f[N];

signed main(){
	Ios;
	cin >> n >> m >> r; 
	
	for(int i=1;i<=n;i++) cin >> a[i].day >> a[i].cnt >> a[i].price;
	
	int idx = 0;
	while(m--)
	{
		int x, y; cin >> x >> y;
		for(int i=1;i<=y;i++) b[++idx] = x;
	}
	sort(b+1, b+idx+1);
	
	for(int i=1;i<=idx;i++) f[i] = 1e18;
	for(int i=1;i<=n;i++) pos[i] = 1;
	
	for(int i=1;i<=idx;i++)
	{
		for(int j=1;j<=n;j++)
		{
			while(pos[j] < i && (b[i] - b[pos[j]] + 1 > a[j].day || i - pos[j] + 1 > a[j].cnt))
				pos[j] ++; //找到第一个满足的位置就停下
			
			f[i] = min(f[i], f[pos[j]-1] + a[j].price); //从其前一位置来转移
		}
	}
	cout << f[idx];
	
	return 0;
}