题目传送门
题目大意： 在一个棋盘上，你要从 ( 1 , 1 ) (1,1) (1,1) 走到 ( n , m ) (n,m) (n,m)，只能向右或向下走，每一个格子有一个事件，你可以选择触发或不触发，如果触发你可以得到 v a l i , j val_{i,j} vali,j 的收益，并且得到一个 b u f f i , j buff_{i,j} buffi,j，在这个 b u f f buff buff 的加成下，每走一步会获得 b u f f i , j buff_{i,j} buffi,j 的收益，直到下一次触发事件，身上的 b u f f buff buff 才会改变，求最大收益。
考虑上一个触发事件的位置，容易得到一个方程： f i , j = max { f x , y + b u f f x , y ( i − x + j − y ) + v a l x , y } f_{i,j}=\max\{f_{x,y}+buff_{x,y}(i-x+j-y)+val_{x,y}\} fi,j=max{fx,y+buffx,y(i−x+j−y)+valx,y}
拆一下： f i , j = max { b u f f x , y ( i + j ) + f x , y − b u f f x , y ( x + y ) + v a l x , y } f_{i,j}=\max\{buff_{x,y}(i+j)+f_{x,y}-buff_{x,y}(x+y)+val_{x,y}\} fi,j=max{buffx,y(i+j)+fx,y−buffx,y(x+y)+valx,y}
这变成了一个类似 y = k x + b y=kx+b y=kx+b 的形式，用李超线段树维护出所有 x , y x,y x,y 对应的直线，然后每次询问找横坐标为 i + j i+j i+j 时，纵坐标的最大值即可。
如果 x , y x,y x,y 能对 i , j i,j i,j 产生贡献，那么需要满足： { x ≤ i y ≤ j \begin{cases} x\leq i\\ y\leq j \end{cases} {x≤iy≤j
这是一个偏序关系，再套一个cdq分治，每层就可以像上面说的那样来做了。
代码如下：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxn 100010 int n,m; struct par{int x,y,id,val,buff;}a[maxn],b[maxn]; struct func{ int k,b,l,r; int calc(int x){return k*x+b;} }; double meet(func x,func y){return 1.0*(y.b-x.b)/(x.k-y.k);} #define zuo ch[0] #define you ch[1] struct node{ int l,r,mid;func z;node *ch[2]; node(int x,int y):l(x),r(y),mid(l+r>>1){ z.l=-1;if(x<y){ zuo=new node(l,mid); you=new node(mid+1,r); }else zuo=you=NULL; } void clear(){ z.l=-1; if(zuo&&zuo->z.l!=-1)zuo->clear(); if(you&&you->z.l!=-1)you->clear(); } void insert(func x){ if(x.l<=l&&x.r>=r){ if(z.l==-1)z=x; else if(x.calc(l)-z.calc(l)>0&&x.calc(r)-z.calc(r)>0)z=x; else if(x.calc(l)-z.calc(l)>0||x.calc(r)-z.calc(r)>0){ if(x.calc(mid)>z.calc(mid))swap(x,z); if(x.k!=z.k)ch[meet(x,z)-mid>1e-8]->insert(x); } }else{ if(x.l<=mid)zuo->insert(x); if(x.r>=mid+1)you->insert(x); } } int ask(int x){ int re=(z.l!=-1?z.calc(x):0); if(l==r)return re; return max(re,ch[x>=mid+1]->ask(x)); } }*root=NULL; int f[maxn]; bool cmp(par x,par y){return x.y<y.y;} void cdq(int l,int r){ if(l==r)return; int mid=l+r>>1;cdq(l,mid); for(int i=l;i<=r;i++)b[i]=a[i]; sort(b+l,b+mid+1,cmp);sort(b+mid+1,b+r+1,cmp); int x=l,y=mid+1,now=0; root->clear(); while(x<=mid&&y<=r){ if(b[x].y<=b[y].y){ root->insert((func){b[x].buff,f[b[x].id]-b[x].buff*(b[x].x+b[x].y)+b[x].val,1,n+m}); x++; }else{ f[b[y].id]=max(f[b[y].id],root->ask(b[y].x+b[y].y)); y++; } } while(y<=r){ f[b[y].id]=max(f[b[y].id],root->ask(b[y].x+b[y].y)); y++; } cdq(mid+1,r); } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int id=(i-1)*m+j; a[id].x=i;a[id].y=j;a[id].id=id; scanf("%d",&a[id].buff); } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&a[(i-1)*m+j].val); } } root=new node(1,n+m); cdq(1,n*m); printf("%d",f[n*m]); }