Mayflyyh
Mayflyyh
MayFlyyh's Blog
ARC 67F Yakiniku Restaurants 题解

ATCODER ARC 67F Yakiniku Restaurants 题解

有编号从1NN家烧烤店,烧烤店在一条线上按照编号顺序排序,第i家烧烤店与第i + 1家烧烤店的距离是A_i

你有编号从1MM张烧烤券,不管是在哪一家烧烤店都可用烧烤券来吃烧烤,在第i家烧烤店用烧烤券j可以吃到一顿美味度为B_{i,j}的烧烤,每一张烧烤券只能使用一次,但是在一家烧烤店你可以使用任意多张烧烤券。

数据范围: 输入的数字都是整数 2 <= N <= 5 * 10^3 1 <= M <= 200 1 <= A_i <= 10^9 1 <= B_{i,j} <= 10^9

你想从自己选择的一家烧烤店开始(随意选择一个开始),然后不断地用未使用的烧烤券去另一家烧烤店。你最终的幸福值是所吃所有烧烤的美味度减去所走的总路程。求最大可能的最终幸福值( M张券必须用完)。

算法一:考虑枚举左右端点l,r,然后取每张券在[l,r]内的最大值。复杂度大概是n^2*m以上了。

算法二:

考虑只枚举左端点,并且每次从左端点往右走。

如果起始点在i,每往左走一步,美味度的变化量是max(0,b[i+1][j]-b[i][j]),说明对于一个餐券,能使美味度变化的点,能够构成一个最长上升序列。对于多张券亦是如此,所以维护一个数组der[i],用来表示从i-1i美味度增加的总量。

对于一般情况,不妨设当前的左端点为l​,当前走到了i​,那么对于第j​张券,

mx_{j}=max(b[k][j]) l\leq j \leq i ,那么从i走到i+1的增量就是max(0,b[i+1][j]-mx_j)

那么现在的der[i+1]=\sum_{j=1}^{m}b[i+1][j]-mx_j,不难发现,这个式子是与我们枚举的l有关的。(因为mx_jj的范围是与l相关联的。

想到我们刚才说的性质,能够做出贡献的点,也就一是b[i+1][j]>0的点。(昨天就是卡在这里)

那么我们不如倒着枚举l,然后对于每张餐券,都用单调栈维护一个单调递增序列,这个单调递增序列便是我们想要的最长上升序列。(从栈顶到栈底递减)

对于一个数值,如果它的插入破坏了单调性质,也就是大于单调栈的栈顶,那么栈顶这个值就不会再做出贡献了,弹出即可。

对于进栈出栈对应维护其在der[i]数组的贡献就好,具体你看代码肯定就懂了。

#include<bits/stdc++.h>
#define ll long long
const int N = 5010;
ll a[N],ans,der[N],b[N][N>>3];
int n,m;
struct sta{
    int top,s[N];
}sta[N>>3];
int main(){
    scanf("%d %d",&n,&m);
    for(int i=2;i<=n;++i)
        scanf("%lld",&a[i]);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)
            scanf("%lld",&b[i][j]);
    }
    for(int i=n;i;--i){
        ll now=0;
        for(int j=1;j<=m;++j){
            while(sta[j].top&&b[i][j]>=b[sta[j].s[sta[j].top]][j]){
                if(sta[j].top>1)
                    der[sta[j].s[sta[j].top-1]]-=b[sta[j].s[sta[j].top-1]][j]-b[sta[j].s[sta[j].top]][j];
                sta[j].top--;
            }
            if(sta[j].top>=1)
                der[sta[j].s[sta[j].top]]+=b[sta[j].s[sta[j].top]][j]-b[i][j];
            sta[j].s[++sta[j].top]=i;
            now+=b[i][j];
        }
        //int now=0;
        ans=std::max(now,ans); 
        for(int j=i+1;j<=n;++j){
            now+=der[j];
            now-=a[j];
            ans=std::max(now,ans);
        }
    }
    printf("%lld",ans);
    return 0;
} 
本文链接:http://www.mayflyyh.com/archives/607
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
没有标签
首页      未分类      ARC 67F Yakiniku Restaurants 题解
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

Captcha Code

MayFlyyh's Blog

ARC 67F Yakiniku Restaurants 题解
ATCODER ARC 67F Yakiniku Restaurants 题解 有编号从$1$到$N$的$N$家烧烤店,烧烤店在一条线上按照编号顺序排序,第$i$家烧烤店与第$i + 1$家烧烤店的距离是$A_i$ 。 你有编号…
扫描二维码继续阅读
2018-12-28