[DS记录]AT2289 [ARC067D] Yakiniku Restaurants
command_block
2021-05-17 10:48:16
**题意** : 在一条街道上有 $n$ 家烧烤店，由近至远编号为 $1\sim n$。第 $i$ 家与第 $i+1$ 家店的距离为 $A_i$。
初始时，你手上有编号为 $1\sim m$ 的烧烤卷各一张。
第 $i$ 家店使用编号为 $j$ 的烧烤卷可以获得的收益为 $B_{i,j}$ ，每张卷只能用一次。
你可以任选一家店作为起点出发，用完所有 $m$ 张卷。
求 吃烧烤的收益减去行走的路程 的最大值。
$n\leq 5000,m\leq 200$ ，时限$\texttt{2s}$。
------------
显然，能到访的店是一个区间，则从区间的某一端开始，总路程最短。
令第 $1$ 家烧烤店的坐标为 $0$ ，用 $A$ 计算出每家烧烤店的坐标。
考虑逐渐增大右端点 $r$，并维护每个左端点 $l$ 的贡献。
记 $F_{l,j}$ 表示在区间 $[l,r]$ 内使用卷 $j$ 所能获得的最大收益。
那么在区间 $[l,r]$ 所能获得的最大收益即为 $H_l=A_r-A_l+\sum_{j=1}^mF_{l,j}$。
考虑如何维护 $F$ 和 $W$。
对于每张卷，使用单调栈维护 $F_{\_,j}$ ，则可以将修改转化为 $O(n)$ 次区间加法。
将区间加法转化为差分，可以 $O(nm)$ 维护 各个 $F_{\_,j}$ 的差分数组。
当然也可以得到 $\sum_{j=1}^mF_{l,j}$ 的差分数组。
对于每个 $r$ ，枚举 $l$ 并更新答案即可。利用差分计算 $\sum_{j=1}^mF_{l,j}$。
复杂度为 $O\big(n(n+m)\big)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 5050
#define MaxM 205
using namespace std;
int n,m,a[MaxN][MaxM],stk[MaxM][MaxN],top[MaxM];
ll x[MaxN],o[MaxN];
int main()
{
scanf("%d%d",&n,&m);
for (int i=2;i<=n;i++){
scanf("%lld",&x[i]);
x[i]+=x[i-1];
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
ll ans=0;
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
while(top[j]&&a[i][j]>=a[stk[j][top[j]]][j]){
int p=stk[j][top[j]];
o[stk[j][top[j]-1]+1]-=a[p][j];
o[p+1]+=a[p][j];
top[j]--;
}stk[j][++top[j]]=i;
o[stk[j][top[j]-1]+1]+=a[i][j];
o[i+1]-=a[i][j];
}
ll sav=0;
for (int l=1;l<=i;l++){
sav+=o[l];
ans=max(ans,sav-(x[i]-x[l]));
}
}printf("%lld",ans);
return 0;
}
```