文档章节

BZOJ1229 & 洛谷2917:[USACO2008 NOV]toy 玩具 & 洛谷4480:[BJWC2018]餐巾计划问题——题解

o
 osc_z1hvg4cu
发布于 2018/04/24 20:14
字数 920
阅读 23
收藏 0

精选30+云产品,助力企业轻松上云!>>>

标题很长emmm……

[USACO2008 NOV]toy 玩具

https://www.luogu.org/problemnew/show/P2917

https://www.lydsy.com/JudgeOnline/problem.php?id=1229

[BJWC2018]餐巾计划问题

https://www.luogu.org/problemnew/show/P4480

其中[BJWC2018]餐巾计划问题的数据范围更大,且数据强度可能更强,因此下文围绕该问题展开。

一个餐厅在相继的n天里,每天需用的餐巾数不尽相同。假设第i天(i=1,2,...,n)(i=1,2,...,n)需要ri块餐巾。餐厅可以在任意时刻购买新的餐巾,每块餐巾的费用为p。

使用过的旧餐巾,则需要经过清洗才能重新使用。把一块旧餐巾送到清洗店A,需要等待m1天后才能拿到新餐巾,其费用为c1;把一块旧餐巾送到清洗店B,需要等待m2天后才能拿到新餐巾,其费用为c2。

例如,将一块第k天使用过的餐巾送到清洗店A清洗,则可以在第k+m1天使用。

请为餐厅合理地安排好n天中餐巾使用计划,使总的花费最小。

对于50%的数据,我们有一个很经典的网络流做法洛谷1251:[网络流24题]餐巾计划问题

但是数据规模扩大后就显然不能用网络流求解了。

分两种情况:

1.快洗店更贵:

考虑到先买和后买餐巾所对答案和过程不会造成影响,且当买餐巾c条达到最优解时,显然c+k的花费比c+k+1的花费更少。

并且不难感性证出c-k的花费比c-k-1的花费更少(会在最优情况下多次使用快洗店的餐巾使得钱变多)。

因此这是一个单峰函数,我们可以三分求解。

最便宜的显然是先使用新的毛巾,等到没了的时候使用慢洗店的,最差使用快洗店的得出答案,使用队列维护一下即可(虽然这么说,也是挺恶心的,我对着别人的代码调了3h才过,可能现在让我解释代码都解释不明白。)

2.快洗点更便宜:

那就都快洗,这是显然的。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=200010;
const int INF=2147483647;
inline int read(){
    int X=0,w=1;char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')X=(X<<1)+(X<<3)+ch-'0',ch=getchar();
    return X*w;
}
int t[N],num[N],q[N],cnt,d,n1,n2,c1,c2,tc;
int sn,sm,so,en,em,eo;
inline void add(int x,int p){
    q[en]=x;num[en++]=p;
}
int f(int k){
    sn=sm=so=en=em=eo=0;
    int ans=(tc-c2)*k;
    add(-2000000,k);
    for(int i=1;i<=d;i++){
        int j=t[i];
        while(sn!=en&&i-q[sn]>=n1){
            num[em]=num[sn];
            q[em++]=q[sn++];
        }
        while(sm!=em&&i-q[sm]>=n2){
            num[eo]=num[sm];
            q[eo++]=q[sm++];
        }
        while(j>0){
            if(so!=eo){
                if(num[eo-1]>j){
                    ans+=c2*j;
                    num[eo-1]-=j;
                    break;
                }
                else{
                    ans+=c2*num[eo-1];
                    j-=num[eo-1];
                    eo--;
                }
            }
            else if(sm!=em){
                if(num[em-1]>j){
                    ans+=c1*j;
                    num[em-1]-=j;
                    break;
                }
                else{
                    ans+=c1*num[em-1];
                    j-=num[em-1];
                    em--;
                }
            }
            else return INF;
        }
        add(i,t[i]);
    }
    return ans;
}
int sfen(int l,int r){
    while(233){
        if(r-l<=2){
            int m=INF;
            for(int i=l;i<r;i++)m=min(m,f(i));
            return m;
        }
        int mid1=l+(r-l)/3,mid2=l+2*(r-l)/3;
        int a=f(mid1);
        if(a!=INF&&a<=f(mid2))r=mid2;
        else l=mid1;
    }
}
int main(){
    d=read(),n1=read(),n2=read(),c1=read(),c2=read(),tc=read();
    if(n1>n2){swap(n1,n2);swap(c1,c2);}
    if(c1<=c2)n2=2000001,c2=101;
    int tsum=0;
    for(int i=1;i<=d;i++){
        t[i]=read();tsum+=t[i];
    }
    printf("%d\n",sfen(0,tsum+1));
    return 0;
}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者:luyouqi233。               +

+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
「题单」网络流『最大流/最小割』

由于最大流=最小割这里不另起一博客但会标记 模板/假模板 洛谷P1343 地震逃生『提高+/省选-』『最大流』 题解洛谷P2740 [USACO4.2]草地排水Drainage Ditches『提高+/省选-』『最大流』洛谷P...

osc_nlxf5cjq
2018/12/12
8
0
LCT总结——应用篇(附题单)(LCT)

为了优化体验(其实是强迫症),蒟蒻把总结拆成了两篇,方便不同学习阶段的Dalao们切换。 LCT总结——概念篇戳这里 题单 灰常感谢XZY巨佬提供的强力资磁!(可参考XZY巨佬的博客总结)题单对...

osc_3md1xrlp
2018/08/18
4
0
各种反演细节梳理&模板

炫酷反演魔术课件byVFKstO FDF Orz(证明全有%%%) 莫比乌斯反演 $F(n)=sumlimits{d|n}f(d)Rightarrow f(n)=sumlimits{d|n}mu(frac n d)F(d)$$F(n)=sumlimits{n|d}f(d)Rightarrow f(n)=sumli......

osc_jfetyty1
2019/01/26
1
0
LCT总结——应用篇(附题单)(LCT)

为了优化体验(其实是强迫症),蒟蒻把总结拆成了两篇,方便不同学习阶段的Dalao们切换。 LCT总结——概念篇戳这里 题单 灰常感谢XZY巨佬提供的强力资磁!(可参考XZY巨佬的博客总结) 题单对...

Flash_Hu
2018/08/18
0
0
DP的各种优化(动态规划,决策单调性,斜率优化,带权二分,单调栈,单调队列)

前缀和优化 当DP过程中需要反复从一个求和式转移的话,可以先把它预处理一下。运算一般都要满足可减性。 比较naive就不展开了。 题目 【Todo】洛谷P2513 [HAOI2009]逆序对数列 【Done】洛谷P...

Flash_Hu
2018/08/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

linux下java环境搭建

1、jdk下载: 官方地址:https://www.oracle.com/java/technologies/javase/javase-jdk8-downloads.html 如下图所示,我这边选择的是红框中的版本 2、压缩包上传至服务器 将下载的压缩包上传...

wc_飞豆
35分钟前
17
0
面试题:Java对象不再使用时,为什么要赋值为null?

前言 许多Java开发者都曾听说过“不使用的对象应手动赋值为null“这句话,而且好多开发者一直信奉着这句话;问其原因,大都是回答“有利于GC更早回收内存,减少内存占用”,但再往深入问就回...

码农突围
37分钟前
22
0
设计模式(5) 原型模式

原型模式 原型模式的适用场景 浅拷贝 深拷贝 用Initialize方法修改初始化状态 原型模式与之前学习的各种工厂方法、单例模式、建造者模式最大、最直观的区别在于,它是从一个既有的对象“克隆...

zhixin9001
37分钟前
7
0
获取免费的pycharm激活码网站

http://www.lookdiv.com/

云烟成雨forever
37分钟前
27
0
用Helm部署Kubernetes应用,支持多环境部署与版本回滚

1 前言 Helm是优秀的基于Kubernetes的包管理器。利用Helm,可以快速安装常用的Kubernetes应用,可以针对同一个应用快速部署多套环境,还可以实现运维人员与开发人员的职责分离。现在让我们安...

南瓜慢说
39分钟前
25
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部