洛谷p2669_洛谷首页

洛谷p2669_洛谷首页洛谷 2577 [ZJOI2005]午餐——序列dp

大家好,又见面了,我是你们的朋友全栈君。

题目:https://www.luogu.org/problemnew/show/P2577

可以从只有一个窗口的角度思考出一个贪心结论。就是应当按吃饭时间(不算打饭时间)从大到小排序。这样交换相邻两个不会使答案更优,因为交换的话对其他人无影响,而吃饭时间长的那个人打到饭的时间也靠后了。

记录第一个窗口打完饭的时间在状态里。已知前 i 个人打饭时间和,能算出来第二个窗口打完饭的时间。所以值就可以记录总共的最晚结束时间了!也因为最晚结束时间对于打完饭的时间不是关系很紧密的,所以需要把第一个窗口的所有可能的打完饭的时间对应的结束时间记录下来。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=205,M=N*N,INF=0x3f3f3f3f;
int n,f[2][M],ans=INF,lm;
struct Node{
    int a,b;
    bool operator< (const Node &v) const
        {
    
    return b>v.b;}
}t[N];
int rdn()
{
    int ret=0,fx=1; char ch=getchar();
    while(ch>'9'||ch<'0'){
   
   if(ch=='-')fx=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();
    return ret*fx;
}
int main()
{
    n=rdn();
    for(int i=1;i<=n;i++) t[i].a=rdn(),t[i].b=rdn();
    sort(t+1,t+n+1);
    memset(f,0x3f,sizeof f); f[0][0]=0;
    for(int i=1,u=1,v=0;i<=n;i++,u=!u,v=!v)
    {
        lm+=t[i].a;
        for(int j=0,k1,k2;j<=lm;j++)
        {
            if(f[v][j])f[u][j]=max(f[v][j],lm-j+t[i].b);
            if(j>=t[i].a)
                f[u][j]=min(f[u][j],max(f[v][j-t[i].a],j+t[i].b));
        }
    }
    int d=(n&1);
    for(int j=0;j<=lm;j++) ans=min(ans,f[d][j]);
    printf("%d\n",ans);
    return 0;
}

 

转载于:https://www.cnblogs.com/Narh/p/9670070.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107300.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 语义分割技术综述_语义分割模型

    语义分割技术综述_语义分割模型综述论文翻译:AReviewonDeepLearningTechniquesAppliedtoSemanticSegmentation近期主要在学习语义分割相关方法,计划将arXiv上的这篇综述好好翻译下,目前已完成了一部分,但仅仅是尊重原文的直译,后续将继续完成剩余的部分,并对文中提及的多个方法给出自己的理解。论文地址:https://arxiv.org/abs/170…

  • Python贪吃蛇 (完整代码+详细注释+粘贴即食)

    Python贪吃蛇 (完整代码+详细注释+粘贴即食)代码#!/usr/bin/envpython#-*-coding:utf-8-*-#author:Wangdalitime:2021年1月24日16:08:44#python实现:贪吃蛇”’游戏玩法:回车开始游戏;空格暂停游戏/继续游戏;方向键/wsad控制小蛇走向”””思路:用列表存储蛇的身体;用浅色表示身体,深色背景将身体凸显出来;蛇的移动:仔细观察,是:身体除头和尾不动、尾部消失,头部增加,所以,新添加的元素放在列表头部、删除尾部元素;游戏结束判定策略:超出

  • pycharm有什么好用的插件_pycharm插件推荐

    pycharm有什么好用的插件_pycharm插件推荐目录一、安装二、导入及设置三、使用一、安装在全局环境中(不要在虚拟环境中安装pipinstallautopep8二、导入及设置在PyCharm导入这个工具,具体设置如下图:Name:AutoPep8Description:autopep8yourcodeProgram:autopep8Arguments:–in-place–aggressive–aggressive$FilePath$Workingdirectory:$ProjectFileDir$

  • 向量的夹角余弦公式_向量空间模型(VSM)的余弦定理公式(用余弦定理来表示向量之间的相似度)…[通俗易懂]

    向量的夹角余弦公式_向量空间模型(VSM)的余弦定理公式(用余弦定理来表示向量之间的相似度)…[通俗易懂]相信很多学习向量空间模型(VectorSpaceModel)的人都会被其中的余弦定理公式所迷惑..因为一看到余弦定理,肯定会先想起初中时的那条最简单的公式cosA=a/c(邻边比斜边),见下图:但是,初中那条公式是只适用于直角三角形的,而在非直角三角形中,余弦定理的公式是:cosA=(c2+b2-a2)/2bc不过这条公式也和向量空间模型中的余弦定理公式不沾边,迷惑..引用吴军老师的数…

    2022年10月28日
  • CentOS 安装 semanage 命令

    CentOS 安装 semanage 命令

    2021年10月18日
  • 【收藏】神器 Nginx 的学习手册

    【收藏】神器 Nginx 的学习手册点击上方阿拉奇学Java,选择设为星标优质文章,及时送达来源:blog.csdn.net/yujing1314/article/details/107000737Nginx是一个高性…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号