AW302 任务安排3

本文主要是介绍AW302 任务安排3，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址

---

易错点：

• 需要熟练掌握斜率优化DP的原理与实现方法.
• 二分时需要仔细判定边界条件.

---

#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
const int MAXN=3e5+10;
ll f[MAXN],sumT[MAXN],sumC[MAXN];
int q[MAXN],l=1,r=1;
int binary_search(int k){int L=l,R=r;while(L<R){int mid=(L+R)>>1;if(f[q[mid+1]]-f[q[mid]]<k*(sumC[q[mid+1]]-sumC[q[mid]]))L=mid+1;else R=mid;;}return q[L];
}
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 p=binary_search(s+sumT[i]);f[i]=f[p]+sumT[i]*sumC[i]-sumT[i]*sumC[p]+s*sumC[n]-s*sumC[p];while(l<r&&(f[i]-f[q[r]])*(sumC[q[r]]-sumC[q[r-1]])<=(f[q[r]]-f[q[r-1]])*(sumC[i]-sumC[q[r]]))r--;q[++r]=i;}printf("%lld\n",f[n]);return 0;
}

 

这篇关于AW302 任务安排3的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---