Yakiniku Restaurants
明显在最优方案中，行走方式一定是从一条线段的一端走到另一端，不回头。
于是设 \(f[i,j]\) 表示从 \(i\) 走到 \(j\) 的最优代价。明显，该代价对于不同的券相互独立。故我们依次考虑每一张券。
我们发现，假设有一张位置 \(k\) 的券，则所有 \(k\in[l,r]\) 的 \([l,r]\) 都是可以享受到它的。于是，我们建出笛卡尔树来，就可以把它用差分轻松解决了（假设笛卡尔树上有一个节点 \(x\)，它是区间 \([l,r]\) 中的最大值，则所有区间 \([l,r]\) 中穿过它的区间都会增加 \(a_x\)，但是它的两个子区间 \([l,x-1]\) 和 \([x+1,r]\) 却享受不到，故在该处再减少 \(a_x\)，即可实现差分地更新。
则时间复杂度 \(O(nm+n^2)\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e3+100;
int n,m,tp,res;
int a[210][N],stk[N],l[N],r[N],s[N],f[N][N];
void solve(int id,int x,int L,int R,int las){
f[L][R]+=a[id][x]-las;
if(L==R) return;
if(l[x]) solve(id,l[x],L,x-1,a[id][x]);
if(r[x]) solve(id,r[x],x+1,R,a[id][x]);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=2;i<=n;i++){
cin>>s[i];
s[i]+=s[i-1];
}
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[j][i];
for(int i=1;i<=m;i++){
tp=0;
for(int j=1;j<=n;j++){
l[j]=r[j]=0;
while(tp&&a[i][stk[tp]]<=a[i][j]) l[j]=stk[tp--];
if(stk[tp]) r[stk[tp]]=j;
stk[++tp]=j;
}
solve(i,stk[1],1,n,0);
}
for(int i=1;i<=n;i++)for(int j=n;j>=i;j--) f[i][j]+=f[i-1][j]+f[i][j+1]-f[i-1][j+1];
for(int i=1;i<=n;i++)for(int j=i;j<=n;j++) res=max(res,f[i][j]-(s[j]-s[i]));
cout<<res;
return 0;
}