301. 任务安排2（算法竞赛进阶指南，斜率优化 DP）_算法进阶指南任务安排 2-程序员宅基地

技术标签： # 斜率优化 DP

一.题目链接：

任务安排 2

二.题目大意：

中文题~~

三.分析（划水）：

嘤嘤嘤，第一道斜率优化 DP.

网上讲解很多了，大佬讲得也很棒，我就不造轮子了.

四.代码实现：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;

const int M = (int)3e5;
const int inf = 0x3f3f3f3f;

ll sumt[M + 5];
ll sumc[M + 5];
ll q[M + 5];
ll f[M + 5];

int main()
{
    int n, s;
    scanf("%d %d", &n, &s);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%lld %lld", &sumt[i], &sumc[i]);
        sumt[i] += sumt[i - 1];
        sumc[i] += sumc[i - 1];
    }
    int l = 1, r = 0;
    q[++r] = 0;
    for(int i = 1; i <= n; ++i)
    {
        while(l < r && (f[q[l + 1]] - f[q[l]]) <= (s + sumt[i]) * (sumc[q[l + 1]] - sumc[q[l]]))    ++l;
        if(l <= r)   f[i] = f[q[l]] + sumt[i] * (sumc[i] - sumc[q[l]]) + s * (sumc[n] - sumc[q[l]]);
        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;
}

本文链接：https://blog.csdn.net/The___Flash/article/details/104649046

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

解决docker镜像（centos系统）中无sudo命令_docker 没有sudo-程序员宅基地

文章浏览阅读1w次，点赞2次，收藏7次。问题最新在协助同事在docker中安装app时，提供的container使用了centos基础镜像（某些功能阉割版）：[root@server111-111 admin]# docker imagesREPOSITORY TAG IMAGE ID CREATED SIZ..._docker 没有sudo

LR(1)分析法的总控的实现（C++实现）_输入lr分析表,写出总控程序-程序员宅基地

文章浏览阅读8.9k次，点赞14次，收藏109次。 LR(1)分析法实验设计思想及算法（1）若ACTION[sm , ai] = s则将s移进状态栈，并把输入符号加入符号栈，则三元式变成为：(s0s1…sm s , #X1X2…Xm ai , ai+1…an#)（2）若ACTION[sm , ai] = rj则将第j个产生式A->β进行归约。此时三元式变为(s0s1…sm-r s , #X1X2…Xm-rA , ai..._输入lr分析表,写出总控程序

Max OS下安装brew_max brew-程序员宅基地

文章浏览阅读975次。ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)" < /dev/null 2> /dev/null_max brew

入手分析rtx3070和rtx2080ti哪个强？rtx3070和rtx2080ti性能对比_3070和2080ti哪个好-程序员宅基地

文章浏览阅读1.2w次。RTX3070与2080Ti/2070S性能对比评测首先我们来看看RTX3070这款显卡的参数情况，并加入2080Ti、RTX2070Super、RTX2070这三款显卡进行对比，来看看吧。2020年最新主流台式机组装电脑配置推荐(中高低配置详细推荐) https://diannao.com/ts2020年最佳笔记本电脑是谁？权威媒体发布年度十大推荐笔记本 https://diannao.com/bjb【想要购买笔记本，装机，DIY电脑，或者想换电脑.笔记本怕被坑的小伙伴建议看看】显卡参数对比_3070和2080ti哪个好

Docker Selenium(1) 搭建服務及chrome 使用 firefox_selenium/standalone-firefox-程序员宅基地

文章浏览阅读6.1k次。Docker Selenium能讓Selenium在Docker中運行，可加速建置時間及獨立出各瀏覽器的版本，保持了一定的隔離性，是非常好的測試環境。docker-selenium 官方文檔鏡像介紹selenium/hub: Grid Hub，相當於一個空白的Seleniun Server，selenium/node-chrome: Chrome節點，需加入Grid Hub才能使用。selenium/node-firefox: Firefox節點，需加入Grid Hub才能使用。sele_selenium/standalone-firefox

程序员最后归宿是什么？30或35想转行？_35程序员转行做什么工作-程序员宅基地

文章浏览阅读2.8k次。中学政治学科的课堂上，辩证唯物主义告诉我们，任何事物都包含着既对立又统一的两个方面。要如实的反映事物的本来面目，就必须坚持一分为二的矛盾分析法，对矛盾作全面的分析要运用两分法、两点论去认识事务的本质。简单的意思就是，万事万物都要看到它好的一面和不好的一面。　　IT也是如此，程序员的职业也是如此。“程序员的最后归宿是什么！”、“程序员为什么到了30或35就会想要转行”、“边缘化的IT人”等等诸如_35程序员转行做什么工作

随便推点

学习Vue3 第三十一章（了解UI库ElementUI，AntDesigin等）_vue3 elemrnt-ui ant-d-程序员宅基地

文章浏览阅读7.3k次，点赞7次，收藏25次。作为一款深受广大群众以及尤大崇拜者的喜欢，特此列出在github上开源的vue优秀的UI组件库供大家参考这几套框架主要用于后台管理系统和移动端的制作，方便开发者快速开发安装方法main ts引入volar插件支持。..._vue3 elemrnt-ui ant-d

echarts自定义map背景，以及自定义标注效果_echarts热力registermap 背景透明-程序员宅基地

文章浏览阅读7.7k次，点赞4次，收藏13次。实现思路设置DIV的背景图，为自定义彩图；绘制echarts地图，默认情况下区域颜色透明，没有边框；通过设置aspectScale(宽高比)、center(中心坐标)、zoom(缩放大小)来控制echarts和彩图的重叠效果；设置鼠标浮动到的区域效果，渐变色、背景等等。实现代码js代码const json = require('@/assets/data/guizhou.json')echarts.registerMap('贵州省', json)this.centerMapChart._echarts热力registermap 背景透明

中文分词工具比较 6大中文分词器测试（哈工大LTP、中科院计算所NLPIR、清华大学THULAC和jieba、FoolNLTK、HanLP）_中文分词ltp和jieba哪个更好-程序员宅基地

文章浏览阅读3w次，点赞29次，收藏169次。#!/ Mypython# -*- coding: utf-8 -*-# @Time : 2018/8/5 22:19# @Author : LinYimeng# @File : fenci_ceshi.py# @Software: PyCharmimport timetestCases=[&amp;amp;amp;amp;amp;amp;amp;amp;amp;quot;结婚的和尚未结婚的确实在干扰分词啊&amp;a_中文分词ltp和jieba哪个更好