文档章节

XJOI 迷你火车头

机智的帝江
 机智的帝江
发布于 2016/10/30 09:59
字数 979
阅读 42
收藏 0

题目描述
一列火车有一个火车头拖着一长串的车厢,每个车厢有若干个乘客。一旦火车头出了故障,所有的车厢就只能停在铁轨上了,因此铁路局给每列火车配备了三个迷你火车头,每个迷你火车头可以拖动一定数量的车厢,以便火车头发生故障后能够拖走部分车厢。

铁路部门对迷你火车头作了如下规定:

1.迷你火车头能够拖动的最大车厢数是确定的,这个数量对三个迷你火车头都是相同的。

2.一旦火车头发生故障,迷你火车头要拖走尽可能多的旅客,每节车厢的旅客数事先是已知的,并且旅客不得随意更换车厢。

3.一个迷你火车头拖走的车厢必须是连续的,所有车厢从1开始编号。

假如有7节车厢,一个迷你火车头最多可以拖动二节车厢,1到7号车厢中的旅客人数分别为35,40,50,10,30,45和60。

如果三个迷你火车头拖走的车厢分别是1-2,3-4和6-7,它们带走的旅客总数将达到240人,其它任何方案都不可能超过该数,所以240就是这个问题的解。

给定车厢数,每节车厢的旅客人数和一个迷你火车头能拖动的最大车厢数,写一个程序求出三个迷你火车头最多能带走的旅客数。

输入

输入文件共有三行,第一行为一个正整数n,其中n<=50,000,表示车厢总数,第二行为n个用空格隔开的整数,依次表示n节车厢的旅客人数,每节车厢人数不超过100,第三行为一个正整数m表示迷你火车头能够拖动的最大车厢数,其中m<=n/3。

输出

输出文件仅有一行包含一个整数表示三个迷你火车头最多能带走的旅客数。

样例

样例输入:

7

35 40 50 10 30 45 60

2

样例输出:

240

据说这是个暴力枚举+贪心的水题然而我还是中规中矩的打了DP。。。。。。
贪心的做法:题目等同于选取三个区间,从而使这三个区间和最大。那么显然三个区间不互相覆盖一定是最优的(因为没有负数)。那么我们从第k+1个到第n-k+1枚举中间的火车就好。什么?TLE?没关系!对于整个数组,我们维护一个前缀和,维护一个后缀和,这样我们就能在O(n)的时间内得出答案(常数当然不算)。
DP做法:先预处理出一个小火车头在第i个地点所能载得的人数,然后我们开一个二维dp数组,第一维记录位置,第二维记录第几个小火车头。因为我们有一个小火车头能载得的人数,那么我们能优先处理出dp[i][1]来,这样我们就只需要dp出第二和第三个小火车头就行了。方程也很容易写出:dp[i][j]=max(dp[i-1][j],dp[i-k][j-1]+w[i])
DP的代码

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 55000;
int n,k,a[maxn],dp[maxn][4],w[maxn];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%d",&k);
    for (int i=1;i<=k;i++) w[1]+=a[i];
    for (int i=k+1;i<=n;i++) w[i-k+1]=w[i-k]-a[i-k]+a[i];
    for (int i=1;i<=n-k+1;i++) dp[i][1]=max(dp[i-1][1],w[i]);
    for (int j=2;j<=3;j++)
    for (int i=k*(j-1)+1;i<=n-k+1;i++) 
        dp[i][j]=max(dp[i-1][j],dp[i-k][j-1]+w[i]);
    printf("%d\n",dp[n-k+1][3]);
    return 0;
}

本文转载自:http://blog.csdn.net/loi__dijiang/article/details/49616337

上一篇: Codevs 喝咖啡
下一篇: Codevs 玛丽卡
机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
2019杭电多校第一场hdu6581 Vacation

Vacation 题目传送门 解题思路 一开始的时候所有车都是是按照自己原来的速度行驶,直到有一辆车x追上前面的那辆车y,此时的变化只有,1.x的速度变为y的速度2.x后面的车追上x的时间变短。所以...

whisperlzw
07/23
0
0
Magento采集火车头采集教程

想要快速拥有一个自已的B2C商店吗?还为上传产品的工作而苦恼吗? 大家第一个想到采集-火车头采集! 是的熟悉magento 与火车头采集规则。能实现自动下载上传图片。让你一晚瞬间拥有几万个S...

magento800
2012/11/26
2.4K
0
最新小说网站源码 带会员系统 带3个wap端 火车头自动采集+网页采集

最新小说网站源码 带会员系统 带3个wap端 火车头自动采集+网页采集 笔趣阁:www.xs.520jun.com 自适应手机端:http://www.xs.520jun.com/wap/ 触屏版手机端:http://www.xs.520jun.com/wapt...

myjnt
2018/05/13
0
0
Microsoft Excel 2010--迷你图

迷你图是EXCEL2010中加入的一种全新的图表制作工具,它以单元格为绘图区域,简单便捷的为我们绘制出简明的数据小图表,方便的把数据以小图的形式呈现在读者的面前,它是存在于单元格中的小图...

xiaopei050
2018/06/27
0
0
VB.NET / C# 遍历列出目录下所有文件

VB.NET / C# 遍历列出目录下所有文件 Forece Blog2017-09-2115 阅读 c#VB遍历VB.net VB.NET / C# 遍历列出目录下所有文件 VB 代码...

Forece Blog
2017/09/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Hive详解

1. Hive基本概念 1.1 Hive简介 1.1.1 什么是Hive Hive是基于Hadoop的一个数据仓库工具,可以将结构化的数据文件映射为一张数据库表,并提供类SQL查询功能。 1.1.2 为什么使用Hive 直接使用h...

天子剑毅
14分钟前
1
0
MYSQL 常用命令

打开终端,输入如下命令: /usr/local/MySQL/bin/mysql -u root -p 打开终端,输入如下命令: mysql -h 23.106.134.88 -u root -p 123456 mac启动、停止、重启MySql服务 启动MySql服务:sud...

xiaodong16
17分钟前
2
0
哈希

第一个只出现一次的字符的位置

Garphy
40分钟前
25
0
Centos7.7之离线安装kubectl

Centos7.7,kubernates-1.13.5. 我的Centos7.7上已经安装了kubernates 1.13.5,但是没有kubectl命令,手动安装 浏览器中访问https://storage.googleapis.com/kubernetes-release/release/sta......

克虏伯
42分钟前
35
0
12_多线程

12_多线程 wait():一旦执行此方法,当前线程就进入阻塞状态,并释放同步监视器(释放锁)。 notify():一旦执行此方法,就会唤醒被wait的一个线程。如果有多个线程被wait,就唤醒优先级高的那个...

行者终成事
55分钟前
42
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部