正文
【AtCoder】ARC067 F - Yakiniku Restaurants 单调栈+矩阵差分
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
【题目】F - Yakiniku Restaurants
【题意】给定n和m，有n个饭店和m张票，给出Ai表示从饭店i到i+1的距离，给出矩阵B(i,j)表示在第i家饭店使用票j的收益，求任选起点和终点的最大（收益-代价）。n<=5000,m<=200。
【算法】单调栈+矩阵差分
【题解】直接枚举区间，很难同时计算m张票，我们反过来考虑每个B(i,j)的贡献。
对于B(i,j)，令x为满足x<i,B(x,j)>B(i,j)的最大的x，令y为满足y>i,B(y,j)>B(i,j)的最小的y，则B(i,j)会对所有l∈[x+1,i]&&r∈[i,y-1]的区间贡献。
其中，x和y可以维护单调栈求得。（因为求最大，所以越早越没用）
现在将区间[x,y]视为平面上的点(x,y)，那么就是矩阵加B(i,j)，最后扫描每个点，这个用差分就可以了。
复杂度O(n^2+nm)。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=;
int n,m,b[maxn][maxn],s[maxn],l[maxn][maxn],r[maxn][maxn],w[maxn];
ll a[maxn],A[maxn][maxn];
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%lld",&a[i]),a[i]+=a[i-];
for(int i=;i<=n;i++)for(int j=;j<=m;j++)scanf("%d",&b[j][i]);
for(int i=;i<=m;i++){
int top=;
for(int j=;j<=n;j++){
while(top&&b[i][j]>s[top])top--;
if(top)l[i][j]=w[top]+;else l[i][j]=;
s[++top]=b[i][j];w[top]=j;
}
top=;
for(int j=n;j>=;j--){
while(top&&b[i][j]>s[top])top--;
if(top)r[i][j]=w[top]-;else r[i][j]=n;
s[++top]=b[i][j];w[top]=j;
}
for(int j=;j<=n;j++){
A[l[i][j]][j]+=b[i][j];
A[l[i][j]][r[i][j]+]-=b[i][j];
A[j+][j]-=b[i][j];
A[j+][r[i][j]+]+=b[i][j];
}
}
ll ans=-1ll<<;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++)A[i][j]+=A[i][j-];
for(int j=;j<=n;j++)A[i][j]+=A[i-][j];
for(int j=i;j<=n;j++)ans=max(ans,A[i][j]-a[j]+a[i]);
}
printf("%lld",ans);
return ;
}
【另一解】
枚举左端点L。单看一张饭票，用单调栈预处理f[i]表示最小的x满足x>i&&B(x)>B(i)，那么这张饭票的贡献其实是一个从L开始长度为k的递增位置序列c[]，其中c[i]的贡献是B(c[i])-B(c[i-1])。对于所有饭票都将c[i]的贡献叠加到数组g[]上，那么处理完后g[i]表示区间包含i得到的贡献。此时就可以枚举右端点更新答案。
然后考虑左端点移动删除L，即更新为从L+1开始递增的数字。原来c[1]=L，那么实际上到c[2]就停止了，c[2]需要额外减掉B(c[2])-B(c[1])来消除上次的贡献。这个过程暴力更新，复杂度是正确的，因为只会被最近的比它大的数字引发更新，复杂度O(n^2+nm)。
这种思想是考虑左端点的移动对答案的影响，而非右端点。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define ll long long
using namespace std;
int read(){
int s=,t=;char c;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
const int maxn=;
int n,m,a[][maxn],f[][maxn],s[maxn],w[maxn];
ll A[maxn],g[maxn];
int main(){
n=read();m=read();
for(int i=;i<=n;i++)A[i]=read();
for(int i=;i<=n;i++)for(int j=;j<=m;j++)a[j][i]=read();
int top=;
for(int i=;i<=m;i++){
top=;
for(int j=n;j>=;j--){
while(top&&a[i][j]>=s[top])top--;
if(top)f[i][j]=w[top];else f[i][j]=n+;
s[++top]=a[i][j];w[top]=j;
}
}
for(int i=;i<=m;i++){
int j=;g[]+=a[i][];
while(f[i][j]<=n)g[f[i][j]]+=a[i][f[i][j]]-a[i][j],j=f[i][j];
}
ll ans=-1ll<<,sum=g[];ans=max(ans,sum);
for(int i=;i<=n;i++)ans=max(ans,sum=sum-A[i]+g[i]);
for(int k=;k<=n;k++){
for(int i=;i<=m;i++){
int j=k,pre=;
while(j<=n&&j!=f[i][k-])g[j]+=a[i][j]-a[i][pre],pre=j,j=f[i][j];
g[j]-=a[i][j]-a[i][k-];g[j]+=a[i][j]-a[i][pre];
}
sum=g[k];ans=max(ans,sum);
for(int j=k+;j<=n;j++)ans=max(ans,sum=sum-A[j]+g[j]);
}
printf("%lld",ans);
return ;
}
