2016 acm香港网络赛 F题. Crazy Driver(水题)

原题网址：https://open.kattis.com/problems/driver

Crazy Driver

In the Linear City, there are N gates arranged in a straight line. The gates are labelled from 1 to N. Between adjacent gates, there is a bidirectional road. Each road takes one hour to travel and has a toll fee. Since the roads are narrow, you can only travel from gates to gates but cannot U-turn between gates.

Crazy driver Gary starts at Gate 1 at time 0 and he wants to drive through Gate N while minimizing the cost of travelling. However, Gate i only allows a car to pass through after a certain time Ti. As Gary is crazy, his car will always be traveling on any one of the roads, i.e., it will not stop at a gate. What is the minimum cost for him to drive through Gate N ?

As an example, consider the sample input below. An optimal solution is the following:

Gate 1 to Gate 2 (cost 5)
Gate 2 to Gate 1 (cost 5)
Gate 1 to Gate 2 to Gate 3 (cost 9)
Go between Gate 3 and Gate 4 until 7-th hour (cost 6)
Go to and pass through Gate 5(cost 8)

Input

The first line contains an integer, N(2≤N≤105), the number of gates. The second line has N−1 integers, C1,…,CN−1. Ci (1≤Ci≤106) represents the toll fee of the road between Gate i and Gate i+1. The third line has N integers, T1,…,TN. Ti (0≤Ti≤106) represents the opening time (in hour) for each gate. T1 will always be 0.

Output

Output an integer representing the minimum cost of traveling.

Sample Input 1

Sample Output 1

5 4 2 8

0 2 4 4 8

题意：n个门编号1~n,从门i到i+1有一条双向通路，每条路花费的时间都是1小时，每条路花的路费分别是Ci, 每个门开的时刻分别是Ti，一个司机从门1开到门n，中间不停车，即如果到达门i的时候门没开就必须往返于前面的路上直到门开的时刻，问到门n最少花多少路费。

记录每扇门之前的路的最小路费。

#include <algorithm>

#include <cstring>

#include <string.h>

#include <iostream>

#include <list>

#include <map>

#include <set>

#include <stack>

#include <string>

#include <utility>

#include <vector>

#include <cstdio>

#include <cmath>

#define LL long long

#define N 100005

#define INF 0x3ffffff

using namespace std;

int n;

int c[N];               //门i-1到门i的路费是Ci

int m[N];             //门i之前的路的路费最小值

int t[N];               //每个门开的时刻

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n-;i++) {

        scanf("%d",&c[i]);

        if(i==) m[i]=c[i];

        else m[i]=min(m[i-],c[i]);

    }

      for(int i=;i<n;i++) {

          scanf("%d",&t[i]);

      }

    int tt=;           //当前时刻

    int i=;

    long long ret=;

    while(i<n)

        {

            i++;

            tt++;

            ret+=(long long)(c[i]);

            int tmp=t[i]-tt;                   //离门开还有多久

            while(tmp>){

                tmp-=;

                ret+=(long long)(m[i]*);

                tt+=;

            }

        }

        cout<<ret<<endl;

    return ;

}

巴特西

2016 acm香港网络赛 F题. Crazy Driver(水题)

最新文章

热门文章