Travelling

【问题描述】
山山很喜欢旅行,他坐飞机的次数也非常非常多,所以他成为了空中司机航空公司的会
员,并且有一张白金会员卡。
山山规划了接下来一段时间的行程,他需要坐飞机 n 次,现在空中司机给了他 m 种
优惠政策。
对于第 i 种政策,山山可以花费 ci 元办理一张“Ti 日通飞证”,这样他就可以 在某
个连续的 T i 天内坐飞机不花钱。对于每个政策,山山可以办理很多张这样的通飞证。山山
也可以每次直接购买机票,因为他是白金会员,他只需要花费 k 元就可购得一张机票。
由于山山还只是一名小学生,他的计算能力不是很强,于是他希望你能帮他算出完成行
程所需的最小花费。
【输入格式】
输入文件名为 travelling.in。
第一行为三个正整数 n m k。
第二行为 n 个正整数 a1 ~ an ,表示接下来的 n 次坐飞机分别在 a1 ~ an 天后。
保证这个数列递增且不重复。
接下来 m 行每行两个整数 Ti ci ,表示每种优惠政策中的 T 和 c 值。
【输出格式】
输出文件名为 travelling.out。
输出仅一行一个整数 ans 表示答案。
【样例输入与输出】
travelling.in 3 2 4
1 3 4
2 7
3 8
travelling.out
11
【数据范围与约定】
对于 20%的数据:0 < n <= 1000
对于 50%的数据:0 < n <= 10000
对于 100%的数据:0 < n <= 500000,0 <= m <= 20,0 < k, ci <= 1000,0 < ai<= 10 9 ,0 < ti <= 10 9

令 dp[i] 表示满足前 i 次行程的最小花费,那么第 i 天一定是直接买的机票或者为某个通飞
证有效期的最后一天,易得到一个 DP 方程:

dp[i]=max(dp[i-1]+k,dp[pre(i,j)]+c[j]
其中 pre(i, j) 表示“若第 i 天是第 j 种通飞证有效期的最后一天,之前的第一次不要买票
的行程的编号”。
pre 可以每次二分得到,这样每次转移的复杂度是 O(log n) ,会被卡成 50 分。

其实可以单调栈，因为a一直增加

所以d[j]表示第i-1次第j种优惠的pre值，要得到第i次则可以直接在i-1的基础上加

复杂度O(nm)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int a[500001],t[21],c[21],f[500001],d[500001];
 7 int n,m,k;
 8 int main()
 9 {
10     int i,j;
11     cin>>n>>m>>k;
12     for (i=1; i<=n; i++)
13     {
14         scanf("%d",&a[i]);
15     }
16     for (i=1; i<=m; i++)
17         scanf("%d%d",&t[i],&c[i]);
18     for (i=1; i<=n; i++)
19     {
20         f[i]=f[i-1]+k;
21         for (j=1; j<=m; j++)
22         {
23             int p=a[i]-t[j]+1;
24             while (a[d[j]]<p) d[j]++;
25             f[i]=min(f[i],f[max(d[j]-1,0)]+c[j]);
26         }
27     }
28     cout<<f[n];
29 }