列表

详情

NC219655. TravelingMerchant

描述

There is a long east-west road which has  towns situated along it, numbered  to  from west to east. All towns buy and sell the same kind of goodie. The value of a goodie fluctuates according to a weekly schedule. A town buys and sells a goodie at its value in that town on that particular day. At town , the value of a goodie changes by  every day in the first half of a week, and changes by  every day in the second half of a week. In other words, the value of a goodie at town  is  on Mondays and Sundays,  +  on Tuesdays and Saturdays,   on Wednesdays and Fridays, and  on Thursdays.

A merchant is making a business travel plan. His trip begins at a starting town  and ends at a destination town , visiting each town from  to  (inclusive) exactly once. The merchant starts the trip on a Monday. It takes him exactly one day to travel between adjacent towns and every day he travels to the next town on the path to the destination. He may buy exactly one goodie at a town along the trip and sell that goodie at a town he visits later. He can only buy once and sell once. The merchant would like to know the maximum possible profit of  travel plans with different choices of town  and town .

输入描述

The first line of the input has a single integer . The next  lines each have two integers. The -th line has  and . The next line has a single integer . The following  lines each give a pair of integers  and , representing one travel plan from town  to town . If  the merchant travels west to east, otherwise he travels east to west.

输出描述

For each travel plan, output the maximum profit the merchant can make on a single line. If the merchant cannot make any profit, output .

示例1

输入: 

5
1 2
2 1
5 0
4 -1
7 -2
5
1 5
5 1
3 1
4 5
5 4

输出: 

4
2
2
1
0

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 147ms, 内存消耗: 51108K, 提交时间: 2021-03-23 19:40:15 

#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9, N = 1e5+5;
int n, m, x, y, d[N], v[N], a[10][N], p[10], w[N];
struct T { int mx, mn, qmx, qmn; };
struct xds { int l, r;T a; }t[10][N << 2];
T ud(T a, T b)
{
    T c;
    c.mx = max(a.mx, b.mx),c.mn = min(a.mn, b.mn);
    c.qmx = max(max(a.qmx, b.qmx), b.mx - a.mn),c.qmn = min(min(a.qmn, b.qmn), b.mn - a.mx);
    return c;
}
void build(int ro, int l, int r, int o)
{
    t[o][ro].l = l, t[o][ro].r = r;
    if (l == r)
    {
        t[o][ro].a.mx = a[o][l], t[o][ro].a.mn = a[o][l];
        t[o][ro].a.qmx = -inf, t[o][ro].a.qmn = inf;
        return;
    }
    int mid = (l + r) >> 1;
    build(ro << 1, l, mid, o);
    build(ro << 1 | 1, mid + 1, r, o);
    t[o][ro].a = ud(t[o][ro << 1].a, t[o][ro << 1 | 1].a);
}
T ques(int ro, int l, int r, int o)
{
    if (t[o][ro].l == l && t[o][ro].r == r) return t[o][ro].a;
    int mid = (t[o][ro].l + t[o][ro].r) >> 1;
    if (r <= mid) return ques(ro << 1, l, r, o);
    else if (l > mid) return ques(ro << 1 | 1, l, r, o);
    else return ud(ques(ro << 1, l, mid, o), ques(ro << 1 | 1, mid + 1, r, o));
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);p[0] = 0, p[1] = 0, p[2] = 1, p[6] = 1, p[3] = 2, p[5] = 2, p[4] = 3;
    for (int i = 1 && cin >> n;i <= n;i++) cin >> v[i] >> d[i];
    for (int f = 0;f < 7;f++) for (int i = 1;i <= n;i++) a[f][i] = v[i] + p[((i - f) + 7) % 7] * d[i];
    for (int i = 0;i < 7;i++) build(1, 1, n, i);
    for (cin >> m;m-- && cin >> x >> y;) cout << ((x < y) ? max(0, ques(1, x, y, (x - 1) % 7).qmx) : max(0, -ques(1, y, x, x % 7).qmn)) << '\n';
    return 0;
}

上一题

© 2024 nowcoder.com