AW301 任务安排2 （斜率优化DP）

题目地址

易错点：

• 单调队列一定要分清序号和具体值（例如：q[l]和l）.
• 注意中括号嵌套时的逻辑正确性.
• 要保证斜率单调递增，因此可以直接使用单调队列进行问题求解.

#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int MAXN=4e5;
ll f[MAXN],sumT[MAXN],sumC[MAXN];
int q[MAXN],l=1,r=1;
int main(){
    int n,s;
    scanf("%d%d",&n,&s);
    for(int i=1;i<=n;i++){
        int t,c;
        scanf("%d%d",&t,&c);
        sumT[i]=sumT[i-1]+t;
        sumC[i]=sumC[i-1]+c;
    }
    for(int i=1;i<=n;i++){
        int nowL=q[l],nowR=q[r];
        while(l<r&&(s+sumT[i])*(sumC[q[l+1]]-sumC[nowL])>f[q[l+1]]-f[nowL]){
            l++;
            nowL=q[l],nowR=q[r];
        }
        f[i]=f[nowL]+sumT[i]*sumC[i]-sumT[i]*sumC[nowL]+s*sumC[n]-s*sumC[nowL];
        while(l<r&&(f[i]-f[nowR])*(sumC[nowR]-sumC[q[r-1]])<(f[nowR]-f[q[r-1]])*(sumC[i]-sumC[nowR])){
            r--;
            nowL=q[l],nowR=q[r];
        }
        q[++r]=i;
    }
    printf("%lld
",f[n]);
    return 0;
}