题目描述
一个 $n×m$ 的棋盘，要从左上的 $(1,1)$ 走到右下的 $(n,m)$，只能往右或下走。
走到格子 $(i,j)$ 上时首先会获得一个得分 $val_{i,j}$，然后会面临一个可选的事事件。如果触发，会获得 $buff_{i,j}$ 的持续影响 —— 具体来说，直到触发下一次事件为止，每走一步都会获得 $buff_{i,j}$ 的得分。
求最大的得分。
思路
先考虑一个暴力的 DP：设 $f_{i,j}$ 表示到格子 $(i,j)$ 时的最大得分，容易想到转移方程：
$\large f_{i,j} = \max{f_{k,l}+val_{k,l}+buff_{k,l}×(i-k+j-l)}\ \ \ (1≤k≤i,1≤l≤j,(i,j)≠(k,l))$
把 max 里面的式子的括号里的 $(i,j,k,l)$ 分成两组拆开然后移项：
$\large buff_{k,l}×(i+j)+(f_{k,l}+val_{k,l}+buff_{k,l}×(i+j))$
就变成了一个活脱脱的斜率优化式子！其中 $buff_{k,l}$ 是斜率，$(i+j)$ 是横坐标，剩下的是截距。
注意到横坐标和斜率都不具有单调性，我们可以用李超线段树优化，每个横坐标的答案就是这个位置最高的点。当然也可以 CDQ 分治处理动态凸包。
除了转移的优化，我们还需要注意决策点的处理：「一个位置的答案只能由它之前位置的答案转移过来」，即上面方程中的 $1≤k≤i,1≤l≤j,(i,j)≠(k,l)$。这是一个二维偏序问题，可以用树状数组或者 CDQ 分治处理。
Code
从我个人的角度是比较喜欢 CDQ 分治套李超树的这个写法的，因为它是一个「程序= 数据结构+算法」的结构，有一种艺术和美感在里面。 —— 出题人四糸智乃
由于 potatoler 太菜不会 CDQ 分治，于是献上树状数组套李超线段树的代码。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
#include<vector>
#define int long long
#define fake false
#define lowbit(x) x&(-x)
using namespace std;
const int MaxN = 100005*15;
int n, m, lim, root[MaxN], cntTree, cntSeg=0;
struct SegmentTree{
int ls, rs, highest;
}tree[MaxN*4];
struct Segment{
int k, b;
}segment[MaxN];
vector< vector<int> > val, buff, f;
inline int Read(){
int num = 0, op = 1;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') op = -1;
ch = getchar();
}
while(isdigit(ch)){
num = num * 10 + ch - '0';
ch = getchar();
}
return num * op;
}
inline int Gety(int serial, int x){
return segment[serial].k * x + segment[serial].b;
}
inline void Change(int &x, int l, int r, int serial){
if(!x){
x = ++cntTree;
tree[x].highest = serial;
return;
}
// optimize below
if(Gety(tree[x].highest, l) < Gety(serial, l)){
if(Gety(tree[x].highest, r) < Gety(serial, r)){
tree[x].highest = serial;
return;
}
}
else{
if(Gety(tree[x].highest, r) > Gety(serial, r)) return;
}
// optimize above
int mid = (l+r) >> 1;
if(segment[tree[x].highest].k < segment[serial].k){
if(Gety(tree[x].highest, mid) <= Gety(serial, mid)){
Change(tree[x].ls, l, mid, tree[x].highest);
tree[x].highest = serial;
}
else Change(tree[x].rs, mid+1, r, serial);
}
else if(segment[tree[x].highest].k > segment[serial].k){
if(Gety(tree[x].highest, mid) <= Gety(serial, mid)){
Change(tree[x].rs, mid+1, r, tree[x].highest);
tree[x].highest = serial;
}
else Change(tree[x].ls, l, mid, serial);
}
else if(segment[tree[x].highest].b < segment[serial].b) tree[x].highest = serial;
return;
}
inline int Ask(int x, int l, int r, int pos){
if(!x) return 0;
int res = Gety(tree[x].highest, pos);
if(l == r) return res;
int mid = (l+r) >> 1;
if(pos <= mid) return max(res, Ask(tree[x].ls, l, mid, pos));
else return max(res, Ask(tree[x].rs, mid+1, r, pos));
}
inline void Modify(int x, int serial){
while(x<=m){
Change(root[x], 1, lim, serial);
x += lowbit(x);
}
return;
}
inline int Query(int x, int pos){
int res = -LLONG_MAX;
while(x){
res = max(res, Ask(root[x], 1, lim, pos));
x -= lowbit(x);
}
return res;
}
signed main(){
n = Read(), m = Read();
lim = n + m;
val.resize(n+1);
buff.resize(n+1);
f.resize(n+1);
for(int i=1; i<=n; i++){
val[i].resize(m+1);
buff[i].resize(m+1);
f[i].resize(m+1);
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
buff[i][j] = Read();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
val[i][j] = Read();
segment[0] = (Segment){0,0};
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(i == 1 && j == 1){
Modify(1, 0);
continue;
}
cntSeg++;
f[i][j] = Query(j, i+j);
segment[cntSeg].k = buff[i][j];
segment[cntSeg].b = f[i][j] + val[i][j] - buff[i][j] * (i+j);
Modify(j, cntSeg);
}
}
printf("%lld", f[n][m]);
return 0;
}