【题解】Atcoder ARC#67 F-Yakiniku Restaurants

　　觉得我的解法好简单，好优美啊QAQ

　　首先想想暴力怎么办。暴力的话，我们就枚举左右端点，然后显然每张购物券都取最大的值。这样的复杂度是 \(O(n ^{2} m)\) 的。但是这样明显能够感觉到我们重复计算了很多东西，因为区间 \((l, r)\) 的答案与区间 \((l + 1, r)\) 的答案并不是独立的。

　　我们可以考虑一下扫描线的做法。用一根扫描线从右往左扫左端点，同步维护所有以 \(l\) 为左端点的区间。由于我们现已经求出了所有以 \(l + 1\) 为左端点的区间答案（这里的答案指从 \(l -> r\) 中吃东西所能获得的最大权值），我们可以求出 \(l + 1, r\) 到 \(l, r\) 的增量变化，那么 \(ans[l][r] = ans[l + 1][r] + t\)。

　　这个答案的增量显然只与 \(l\) 端点所能获得的权值有关。考虑第 j 个购物券，我们可以维护一个值单调递增的单调栈表示在每一个地点使用 j 购物券能获得最大权值的区间。弹栈的时候，我们用 \(val[i][j] - S[j][top].num\) 即可求出增量。这个增量会增加在 \(ans[i][j] -> ans[i][k]\) 这样的一个区间中。差分就可以解决了。

　　感觉自己讲起来好混乱啊……すみません……

#include <bits/stdc++.h>

using namespace std;

#define maxn 5005

#define int long long

#define maxm 250

int n, m, dis[maxn], val[maxn][maxm];

int Ans, ans[maxn][maxn], Q[maxn];

int read()

{

    int x = , k = ;

    char c; c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

struct node

{

    int num, id;

    node(int _id = , int _num = ) { num = _num, id = _id; }

}S[maxm][maxn];

signed main()

{

    n = read(), m = read();

    for(int i = ; i <= n; i ++) dis[i] = read() + dis[i - ];

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

        for(int j = ; j <= m; j ++) val[i][j] = read();

    for(int i = ; i <= m; i ++) S[i][].id = n + ;

    for(int i = n; i >= ; i --)

    {

        for(int j = ; j <= m; j ++)

        {

            int top = Q[j];

            ans[i][i] += val[i][j]; ans[i][i + ] -= val[i][j];

            while(top && S[j][top].num <= val[i][j])

            {

                int l = S[j][top].id, r = S[j][top - ].id;

                int t = val[i][j] - S[j][top].num;

                ans[i][l] += t, ans[i][r] -= t;

                top --;

            }

            S[j][++ top] = node(i, val[i][j]);

            Q[j] = top;

        }

    }

    for(int i = n; i; i --)

    {

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

            ans[i][j] += ans[i][j - ];

        for(int j = i; j <= n; j ++) ans[i][j] += ans[i + ][j];

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

            Ans = max(Ans, ans[i][j] - dis[j] + dis[i]);

    }

    printf("%lld\n", Ans);

    return ;

}

巴特西

【题解】Atcoder ARC#67 F-Yakiniku Restaurants

最新文章

热门文章