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

约定不等于承诺〃 2021-11-17 16:22 335阅读 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 条评论，335人围观）

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

相关阅读

相关动态规划：空间优化技巧以及接龙型动态规划

空间优化方法滚动数组 > 如果状态依赖关系只在相邻的几层之间，则可以使用滚动数组进行优化 > 滚动数组可以让空间复杂度降维坐标型动态规划使用滚动数组

左手的ㄟ右手/ 2022年11月11日 13:18/ 0 赞/ 175 阅读

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

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

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

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

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

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

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

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

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

相关设计者如何安排开发任务

> > > > > > > 设计者如何安排开发任务

Myth丶恋晨/ 2022年06月18日 00:18/ 0 赞/ 183 阅读

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

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

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

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

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

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

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

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

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

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

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

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

相关 2018任务安排

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

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