luoguP2365 任务安排斜率优化 + 动态规划

约定不等于承诺〃 2021-11-17 16:22 353阅读 0赞

Code:

#include<bits/stdc++.h>
    #define setIO(s) freopen(s".in","r",stdin) 
    #define ll long long 
    #define x(i) (sumf[i]) 
    #define y(i) (f[i]) 
    #define maxn 1000000 
    using namespace std; 
    int n,s,head,tail;
    int q[maxn];  
    ll sumt[maxn],sumf[maxn],f[maxn];   
    double slope(int i,int j) { return (double)(1.00*(y(i)-y(j)))/(double)(1.00*(x(i)-x(j)));}
    int main()
    { 
        // setIO("input"); 
        int i,j; 
        scanf("%d%d",&n,&s); 
        for(i=1;i<=n;++i) 
        {
            scanf("%lld%lld",&sumt[i],&sumf[i]); 
            sumt[i]+=sumt[i-1],sumf[i]+=sumf[i-1]; 
        }
        head=tail=0; 
        for(i=1;i<=n;++i) 
        {
            while(head<tail&&slope(q[head],q[head+1])<=sumt[i]+s)++head; 
            f[i]=y(q[head])+sumf[i]*sumt[i]+s*sumf[n]-(sumt[i]+s)*x(q[head]);    
            while(head<tail&&slope(q[tail],i)<slope(q[tail-1],i)) --tail; 
            q[++tail]=i; 
        }
        printf("%lld\n",f[n]); 
        return 0; 
    }

转载于:https://www.cnblogs.com/guangheli/p/11141567.html

发表评论取消回复

表情：

评论列表（有 0 条评论，353人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划进阶 — — 斜率优化【3】

动态规划进阶 — — 斜率优化【3】 1 打怪兽问题 ![在这里插入图片描述][64870f8dd11b4fffb0c0830f011521f4.png] 1.

朱雀/ 2024年04月06日 09:27/ 0 赞/ 78 阅读

相关浅谈斜率优化

DP模型形如\\(f(i)=\\max \\\{f(j)+w(i,j)\\\}\\quad(1\\le j<i)\\)的dp状态转移方程，朴素的转移时间复杂度为\\(O

墨蓝/ 2023年06月05日 08:55/ 0 赞/ 20 阅读

相关 302 任务安排3（斜率优化）

1. 问题描述：有 N 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。从时刻 0 开始，任务被分

布满荆棘的人生/ 2022年09月15日 12:26/ 0 赞/ 185 阅读

相关 301 任务安排2（斜率优化）

1. 问题描述：有 N 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。从时刻 0 开始，任务被分

深碍√TFBOYSˉ_/ 2022年09月15日 06:08/ 0 赞/ 162 阅读

相关 300 任务安排1（动态规划）

1. 问题描述：有 N 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。从时刻 0 开始，任务被分

╰+攻爆jí腚メ/ 2022年09月15日 05:47/ 0 赞/ 190 阅读

相关『任务安排斜率优化及其变形』

-------------------- 任务安排1 Description \\(N\\)个任务排成一个序列在一台机器上等待完成（顺序不得改变），这\\(N\\

末蓝、/ 2021年12月21日 21:07/ 0 赞/ 270 阅读

相关 luoguP2365 任务安排斜率优化 + 动态规划

Code: include<bits/stdc++.h> define setIO(s) freopen(s".in","r",stdin) de

约定不等于承诺〃/ 2021年11月17日 16:22/ 0 赞/ 354 阅读

相关 BZOJ 1597: [Usaco2008 Mar]土地购买动态规划 + 斜率优化

Code: include<bits/stdc++.h> define maxn 1000000 define ll long long

秒速五厘米/ 2021年11月16日 05:26/ 0 赞/ 258 阅读

相关「斜率优化」学习笔记

当动态规划的状态数为\\(O(n)\\)，每个状态的转移数也是\\(O(n)\\)时，称这种动态规划为1D1D动态规划。对于这种问题，朴素做法是\\(O(n^2)\\)的。

我就是我/ 2021年10月29日 15:38/ 0 赞/ 445 阅读

相关 2018任务安排

完成自己的个人网站 -------------------- 数据库设计接口服务前端界面显示与调整后台管理系统 -----------------

旧城等待，/ 2021年06月24日 16:11/ 0 赞/ 420 阅读