【AtCoder Regular Contest 067 F】Yakiniku Restaurants | Mrsrz's blog

二维差分，单调队列。

题目大意：

数轴上有 $n$ 家店，每家店都有 $1\sim m$ 这 $m$ 种食品，$w_{i,j}$ 表示第 $i$ 家店第 $j$ 种食品的美味度。

你要吃到 $1\sim m$ 的所有食品，并且每种食品只能吃一次。

从一家店走到另一家店，每走一个单位，快乐度降低 $1$。吃美味度为 $W$ 的食品，快乐度也增加 $W$。

最大化最后的快乐度。

题解：

由于是在数轴上，所以肯定是从一家店一直往右吃，到另外一家店停下。

我们考虑对每一对 $l,r$，求出只吃 $l\sim r$ 店的食品的最大快乐度。

我们对每一种食品分别考虑。对于一种食品而言，在 $l\sim r$ 中，肯定选美味度最大的吃。

我们考虑对每一家店的食品 $i$ 求出 $L_i,R_i$ 表示左端点在 $[L_i,i]$，右端点在 $[i,R_i]$ 中时，$i$ 的快乐度都是最大的。且 $[L_i,R_i]$ 是满足条件的极大区间。这可以使用单调队列在 $O(n)$ 内解决。

由于存在快乐度相等，在求的时候可以规定，向左碰到相等时继续，向右碰到相等时停止。

这样，一个食品 $i$ 就会影响到左端点在 $[L_i,i]$，右端点在 $[i,R_i]$ 的矩形区域，而同一种食品的所有矩形是互不相交的。所以可以用差分做矩形加。

最后再 $O(n^2)$ 求出矩形里的所有值，取减去两点距离后的最大方案即可。

时间复杂度 $O(n^2+nm)$。

Code：

#include<cstdio>
#include<algorithm>
const int N=5005;
typedef long long LL;
int n,m;
LL s[N][N],ans,A[N];
int L[N],R[N],sta[N],top;
struct data{
    int B[N];
    void work(){
        L[1]=1,R[n]=n,sta[top=1]=1,sta[0]=0;
        for(int i=2;i<=n;++i){
            while(top&&B[sta[top]]<=B[i])--top;
            L[i]=sta[top]+1;
            sta[++top]=i;
        }
        sta[top=1]=n,sta[0]=n+1;
        for(int i=n-1;i;--i){
            while(top&&B[sta[top]]<B[i])--top;
            R[i]=sta[top]-1;
            sta[++top]=i;
        }
        for(int i=1;i<=n;++i){
            int r1=L[i],c1=i,r2=i,c2=R[i];
            s[r1][c1]+=B[i],s[r1][c2+1]-=B[i];
            s[r2+1][c1]-=B[i],s[r2+1][c2+1]+=B[i];
        }
    }
}d[202];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;++i)scanf("%lld",A+i),A[i]+=A[i-1];
    for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)scanf("%d",&d[j].B[i]);
    for(int i=1;i<=m;++i)d[i].work();
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j){
        s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        if(i<=j&&s[i][j]-A[j]+A[i]>ans)ans=s[i][j]-A[j]+A[i];
    }
    printf("%lld\n",ans);
    return 0;
}