[数据结构与算法] AcWing 300 任务安排1 题解（动态规划—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 300 任务安排1 题解（动态规划—DP—斜率优化DP） -> 正文阅读

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

AcWing 300 任务安排1
解题思路：这题还没上难度，还没有用到斜率优化，将每个任务的时间和花费用前缀和的形式储存，每个任务节点的s都会影响后面的所有节点，所以将这个任务的s的所有影响都算在这一次任务里，用f[i]表示这一批任务结束的任务编号为i，j表示上一批任务的最后一个任务的编号，用前缀和计算公式，求解：
公式：f[i] = min(f[i], f[j] + s * (sumc[n] - sumc[j]) + (sumc[i] - sumc[j]) * sumt[i])

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 5010;

int n, s;
int sumc[N], sumt[N];
int f[N];

signed main()
{
	cin>>n>>s;
	for(int i = 1; i <= n; i ++ ){
		int t, c;
		cin>>t>>c;
		sumc[i] = sumc[i - 1] + c;
		sumt[i] = sumt[i - 1] + t;
	}
	memset(f, 0x3f3f3f3f, sizeof(f));
	f[0] = 0;
	for(int i = 1; i <= n; i ++ ){
		for(int j = 0; j < i; j ++ ){
			f[i] = min(f[i], f[j] + s * (sumc[n] - sumc[j]) + (sumc[i] - sumc[j]) * sumt[i]);
		}
	}
	cout<<f[n]<<endl;
	return 0;
}