文档章节

CodeForces#325 B. Laurenty and Shop

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

点击就送屠龙宝刀

B. Laurenty and Shop

time limit per test 1 second
A little boy Laurenty has been playing his favourite game Nota for quite a while and is now very hungry. The boy wants to make sausage and cheese sandwiches, but first, he needs to buy a sausage and some cheese.

The town where Laurenty lives in is not large. The houses in it are located in two rows, n houses in each row. Laurenty lives in the very last house of the second row. The only shop in town is placed in the first house of the first row.

The first and second rows are separated with the main avenue of the city. The adjacent houses of one row are separated by streets.

Each crosswalk of a street or an avenue has some traffic lights. In order to cross the street, you need to press a button on the traffic light, wait for a while for the green light and cross the street. Different traffic lights can have different waiting time.

The traffic light on the crosswalk from the j-th house of the i-th row to the (j + 1)-th house of the same row has waiting time equal to aij (1 ≤ i ≤ 2, 1 ≤ j ≤ n - 1). For the traffic light on the crossing from the j-th house of one row to the j-th house of another row the waiting time equals bj (1 ≤ j ≤ n). The city doesn’t have any other crossings.

The boy wants to get to the store, buy the products and go back. The main avenue of the city is wide enough, so the boy wants to cross it exactly once on the way to the store and exactly once on the way back home. The boy would get bored if he had to walk the same way again, so he wants the way home to be different from the way to the store in at least one crossing.
Figure to the first sample.
这里写图片描述
Help Laurenty determine the minimum total time he needs to wait at the crossroads.
Input

The first line of the input contains integer n (2 ≤ n ≤ 50) — the number of houses in each row.

Each of the next two lines contains n - 1 space-separated integer — values aij (1 ≤ aij ≤ 100).

The last line contains n space-separated integers bj (1 ≤ bj ≤ 100).
Output

Print a single integer — the least total time Laurenty needs to wait at the crossroads, given that he crosses the avenue only once both on his way to the store and on his way back home.
Sample test(s)
Input

4
1 2 3
3 2 1
3 2 2 3

Output

12

Input

3
1 2
3 3
2 1 3

Output

11

Input

2
1
1
1 1

Output

4

题目大意:你要从(2,n)走到(1,1)点两次,要求路径不完全重复,只能通过中间的过道一次。求最小和。(英语帝勿喷这只是简要的内容)

解题思路:
看到要求最小第一反应是最短路,然而最短路你就废了。比赛时长只有两个小时,如果你跟我一样入了最短路的坑恭喜你起码半小时已经没了。因为过道每次只允许通过一次所以最短路显然不是正解。
现在开始说正解:前缀和。
下面贴代码
(什么??!没听懂???!把图画出来前缀和写出来你就明白了!!)

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;
int a[maxn],b[maxn],c[maxn];
int sa[maxn]= {0},sb[maxn]= {0};
int get(int i)
{
    return sa[i-1]+sb[i]+c[i];
}
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n-1; ++i)
    {
        cin>>a[i];
        sa[i]=sa[i-1]+a[i];
    }
    for(int i=1; i<=n-1; ++i) cin>>b[i];
    for(int i=n-1; i>=1; --i)
    {
        sb[i]=sb[i+1]+b[i];
    }
    for(int i=1; i<=n; ++i) cin>>c[i];
    int ans=99999999999;
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
        {
            if(i==j) continue;
            ans=min(ans,get(i)+get(j));
        }
    cout<<ans<<endl;
    return 0;
}

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

机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
何朝威/zscat_sw

springboot dubbo redis solr mq kafka 商城 blog cms 单机版商城 http://git.oschina.net/JiaGou-XiaoGe/payshop jeeplus单机版商城 https://gitee.com/JiaGou-XiaoGe/jeeplusBanDuoShangJi......

何朝威
2017/10/23
0
0
【mysql】查询过滤器ON,WHERE,HAVING

一、mysql查询的五种子句 where(条件查询)、having(筛选)、group by(分组)、order by(排序)、limit(限制结果数) 1、where常用运算符: 比较运算符 > , < ,= , != (< >),>= , <= in...

SibylY
2013/11/22
456
1
【MySql】1.4 mysql的查询、子查询及连接查询

一、mysql查询的五种子句 where(条件查询)、having(筛选)、group by(分组)、order by(排序)、limit(限制结果数) 1、where常用运算符: 比较运算符: > , < ,= , != (< >),>= ,<= i...

Jannie_xx
2018/06/26
0
0
使用你的mybatis插件 时候碰上一个问题

@miemiedev 你好,想跟你请教个问题:这个分页插件用上后 我期望直接使用shopExample PageBounds pgb = new PageBounds(1,30); ShopExample example = new ShopExample(); example.setDistin......

如是传统
2013/11/08
31.2K
5
一个静态页面如何接收另一个静态页面传过来的值

比如有A、B两个静态页面,其中 A的通过url址址传过来一个值own :http://localhost/ecms/shop_more.html?own=3 即own 现在想让B页面接收own 如何实现...

ziluopao
2016/07/09
1K
6

没有更多内容

加载失败,请刷新页面

加载更多

调用约定

对于常见的指令集,在指令层面没有所谓的“函数”概念,只有“子程序”概念。子程序是存储在“主程序”之外的一段指令。子程序通过call指令调用,通过ret指令返回。子程序可以使用内存、堆栈...

tommwq
38分钟前
3
0
设计类题目

1. 订单 和 退货单之间有什么关系? 答:退货单是 用 用户提交退货 和 订单生成的 或者 订单和退货单都是一张单子,用一个状态标识 2. 在这种由源头单生成的流程中,第二张单子是怎样生成的?...

杨凯123
53分钟前
5
0
读写锁分离

java.util.concurrent.locks包定义了两个锁类, 我们已经讨论的ReentrantLock类和 ReentrantReadWriteLock 类。 如果很多线程从一个数据结构读取数据而很少线程修改其中数 据的话, 后者是十...

ytuan996
今天
6
0
金钱焦虑症测试 -- 人人都有吧?

你经常觉得钱不够花,被金钱困扰着吗?试试这个焦虑量表测试,测试一下你的金钱焦虑指数吧。请选择选一个最适合自己态度的答案。买买买的欲望高吗?又是一个节日,有打折活动;又被种草一个化...

蛤蟆丸子
今天
4
0
JAVA-LOCK之底层实现原理(源码分析)

首先和Synchronized(可以参考) 的不同之处,Lock完全用Java写成,在java这个层面是无关JVM实现的。其实现都依赖java.util.concurrent.AbstractQueuedSynchronizer类,简称AQS。 简单说来,...

小海bug
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部