2020 ICPC沈阳站H题 The Boomsday Project

题目链接：点这里
首先，第一步要把每一次租车当作一次独立的事件提取出来，按照发生的时间进行从小到大排序，就转换为一个线性DP。
$a[i]=p$ 第 $i$ 次租车的天数

$f[i]=f[i-1]+r$ 从上一次租车转移

考虑第 $j$ 种办卡方式对答案的影响

$for(i,1-cnt)//$ 第 $i$ 次租车
$for(j,1-n)//$ 第 $j$ 种办卡方式

假设在处理第 $i$ 次租车办第 $j$ 种卡的影响下考虑第 $j$ 种卡的天数和次数影响下从左往右的临界下标为 $x$ ，即从$x-i-1$都可以通过买第 $j$ 种卡转移到第 $i$ 次租车，复杂度为$O(cnt\times \sum _{j=1}^{n}min(k_j,d_j)\times n)$ 很明显不可行
但是我们的目标仅仅是从临界下标$x-i-1$找到 $min(f[pos])pos\in [x,i-1]$
其实很显然的可以发现整个$dp$数组是单调的（具体也没怎么证）
所以只要取临界值就行了
$f[i]=min(f[i],f[x]+c_j)$
复杂度$O(n\times \sum _{i=1}^m{q}_i)$

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define pii pair<int, int>
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define dep(i, x, y) for(int i = x; i >= y; --i)
#define debug(x) cout << #x": " << x << endl;
#define ct cout << endl;
using namespace std;
const int maxn = 1e6+10;
const ll inf = 1e18;
template <typename _tp>
inline void read(_tp& x) {
char ch = getchar(), sgn = 0;
while (ch ^ '-' && !isdigit(ch)) ch = getchar();
if (ch == '-') ch = getchar(), sgn = 1;
for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
if (sgn) x = -x;
}
struct node{
int d, k, c;
}ty[maxn];
int a[maxn], cnt;
int n, m, r;
int b[maxn], f[maxn];
signed main(){
read(n), read(m), read(r);
rep(i, 1, n) read(ty[i].d), read(ty[i].k), read(ty[i].c);
while(m--){
int p, q;
read(p), read(q);
while(q--) a[++cnt] = p;
}
sort(a+1, a+1+cnt);
rep(i, 1, cnt) f[i] = inf;
rep(i, 1, n) b[i] = 1;
rep(i, 1, cnt){
//debug(i);
f[i] = f[i-1] + r;
rep(j, 1, n){
while(a[b[j]] + ty[j].d <= a[i] || b[j] + ty[j].k <= i) b[j]++;
f[i] = min(f[b[j] - 1] + ty[j].c, f[i]);
//debug(f[i]);
}
}
printf("%lld", f[cnt]);
return 0;
}

最后

以上就是谨慎冬瓜为你收集整理的2020 ICPC沈阳站H题 The Boomsday Project的全部内容，希望文章能够帮你解决2020 ICPC沈阳站H题 The Boomsday Project所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。