Skip to content

14326: 【原4326】市原大辅爱旅行

题目

题目描述

author: Kaname 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4326

问题描述

市原大辅很喜欢旅行,他坐飞机的次数也非常非常多,所以他成为了空中司机航空公司的会员,并且有一张白金会员卡。

市原大辅规划了接下来一段时间的行程,他需要坐飞机$n$次,现在空中司机给了他m种优惠政策。

对于第$i$种政策,市原大辅可以花费$c_i$元办理一张“$T_i$日通飞证”,这样他就可以在某个连续的$T_i$天内坐飞机不花钱。对于每个政策,市原大辅可以办理很多张这样的通飞证。市原大辅也可以每次直接购买机票,因为他是白金会员,他只需要花费$k$元就可购得一张机票。

由于市原大辅还只是一名小学生,他的计算能力不是很强,于是他希望你能帮他算出完成行程所需的最小花费。

输入格式

第一行为三个正整数$n, m, k$。

第二行为$n$个正整数$a_1 \cdots a_n$,表示接下来的$n$次坐飞机分别在$a_1 \cdots a_n$天后。保证这个数列递增且不重复。

接下来$m$行每行两个整数$T_i, c_i$,表示每种优惠政策中的$T$和$c$值。

输出格式

输出仅一行一个整数表示答案。

样例输入

3 2 4
1 3 4
2 7
3 8

样例输出

11

数据范围与约定

对于20%的数据:$0 < n \le 1000$

对于50%的数据:$0 < n \le 10000$

对于100%的数据:$0 < n \le 500000, 0 \le m \le 20, 0 < k, c_i \le 1000, 0 < a_i \le 10^9, 0 < t_i \le 10^9$

zqy2018's solution

#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define MAXN 200005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, k;
int a[500005], cur[25] = {0}, t[25], c[25];
int f[500005];
void init(){
    n = read(), m = read(), k = read();
    REP(i, 1, n)
        a[i] = read();
    REP(i, 1, m)
        t[i] = read(), c[i] = read();
    a[0] = 0;
}
void solve(){
    f[0] = 0;
    REP(i, 1, n){
        f[i] = f[i - 1] + k;
        REP(j, 1, m){
            while (a[cur[j] + 1] <= a[i] - t[j])
                ++cur[j];
            f[i] = min(f[i], f[cur[j]] + c[j]);
        }
    }
    printf("%d\n", f[n]);
}
int main(){
    init();
    solve();
    return 0;
}