暑假集训Day29 H (双指针DP)

题目链接在这里：Problem - H - Codeforces

双指针DP其实就像一个长度可变的滑动窗口，首先因为每一个打折卡都是限定时间和租赁数量的，所以我们把要租的车全部弄开，根据租赁时间从小到大排序，f[i]表示租前i辆车至少要花多少钱，很明显f[i]是递增的，每一次的初始决策是根本不用折扣卡f[i]=f[i-1]+r,然后用折扣卡的话很显然要用一个最小的f[k]来加上c[j]，这里k表示能让第j张卡有效的最前面位置，为了不让每次都从头来找这个k，我们用la[j]来存第j张卡上次用的最后位置，这样直接从上一次用的位置往后枚举就行了。

双指针用与n次具有单调性的查找

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const int MAX=6e5+5;
LL n,m,r;
struct Node{
    LL d,k,c;
}dc[505];
LL sta[MAX];
LL f[MAX],la[505];
int main(){
    freopen ("h.in","r",stdin);
    freopen ("h.out","w",stdout);
    LL i,j,p,q;
    scanf("%lld%lld%lld",&n,&m,&r);
    for (i=1;i<=n;i++){
        scanf("%lld%lld%lld",&dc[i].d,&dc[i].k,&dc[i].c);
        la[i]=1;
    }
    sta[0]=0;
    for (i=1;i<=m;i++){
        scanf("%lld%lld",&p,&q);
        while (q--){sta[++sta[0]]=p;}
    }
    sort(sta+1,sta+sta[0]+1);
    memset(f,0,sizeof(f));
    for (i=1;i<=sta[0];i++){
        f[i]=f[i-1]+r;
        for (j=1;j<=n;j++){
            while (sta[la[j]]+dc[j].d-1<sta[i] || la[j]+dc[j].k-1<i) la[j]++;
            f[i]=min(f[i],f[la[j]-1]+dc[j].c);
        }
    }
    printf("%lld",f[sta[0]]);
    return 0;
}