[数据结构与算法] AcWing 302 任务安排3 题解（动态规划—DP

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> AcWing 302 任务安排3 题解（动态规划—DP—斜率优化DP） -> 正文阅读

[数据结构与算法]AcWing 302 任务安排3 题解（动态规划—DP—斜率优化DP）

AcWing 302 任务安排3
补充上一题的思路：比上一个任务安排2多了一个t小于0的数据范围，所以直线的斜率可能为负，此时就要对队列内的点值进行二分，找到第一个大于新加入的k的k值，找到合适的k值之后，这个点就是i对应的最小的j值
具体题解看这里：
如果没有做任务安排1的话建议先做哪个，看第一步题解
第一步题解
 第二步题解

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 3e5 + 10;

int n, S, m;
int sc[N], st[N];
int q[N];
int f[N];

signed main()
{
	cin>>n>>S;
	for(int i = 1; i <= n; i ++ ){
		cin>>st[i]>>sc[i];
		sc[i] += sc[i - 1];
		st[i] += st[i - 1];
	}
	
	int hh = 0, tt = 0;
	q[0] = 0;
	
	for(int i = 1; i <= n; i ++ ){
		int l = hh, r = tt;
		while(l < r){
			int mid = l + r >> 1;
			if((f[q[mid + 1]] - f[q[mid]]) > (S + st[i]) * (sc[q[mid + 1]] - sc[q[mid]])) r = mid;
			else l = mid + 1;
		} 
		
		int j = q[r];
		f[i] = f[j] - (st[i] + S) * sc[j] + st[i] * sc[i] + S * sc[n];
		while(hh < tt && (double)(sc[i] - sc[q[tt - 1]]) * (f[q[tt]] - f[q[tt - 1]]) >= (double)(f[i] - f[q[tt - 1]]) * (sc[q[tt]] - sc[q[tt - 1]])) tt -- ;
		q[ ++ tt] = i;
	}
	cout<<f[n]<<endl;
	return 0;
}