背景
遇到了一道矩形上的DP,点的处理过后的DP为。其中为。看柿子很斜率优化,但是二维平面上很不好整,打了个暴力就溜了。然后发现这题人均正解,还被教练嘲讽:“这不是套路题吗?”。嘤嘤嘤自闭了。
套路
我们发现转移柿子是形如。分别是只和一个点对相关的柿子。我们发现这是一个斜率优化:我们需要在很多状态中求最大值,而每个状态的大小是由自己本身的性质()和变量组成的。(P.S. 如果还乘了个和相关的柿子,可以把变成然后把提出去)
但是我们考虑,这道题的直线并没有单调性,所以需要两层CDQ,可能还需要个动态凸包啥的(我也没细想)。于是我们考虑使用李超线段树。
李超线段树其实就是维护了一个凸包。凸包上的每条边都代表一个转移状态(一般斜率优化的状态在点上,当然也有状态在边上的写法)。当你确定一个自变量的时候,用这条直线去切凸包,切到的直线就是最优决策。还有一个问题就是这道题从哪里转移过来的限制是一个二维前缀。以递增的顺序计算DP值可以避免坐标的访问越界,但是坐标无法避免。解决方案只有套个树状数组,树状数组每个节点都代表了一个区间,对每个树状数组节点都建个李超树即可。(其实就是树套树)
需要注意的是:我们用树状数组维护的那一维是尽量小的那一维,这样我们的时间就能少一些。
时间复杂度:
空间复杂度:
代码:
/*
_|_| _| _| _|
_| _| _| _|_| _|_|_|_| _| _| _|
_| _| _|_| _| _| _|_|
_| _| _| _| _| _| _| _|
_|_| _| _|_|_|_| _|_| _| _|
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=1e5+1000;
const ll inf=1e18;
int buff[maxn],val[maxn];
int bk1[maxn],bk2[maxn];
int n,m;
int get_id(int i,int j,int g=m){return (i-1)*g+j;}
struct line{
int k;ll b;
ll get(int x){return 1ll*x*k+b;}
};
line mk_l(int k,ll b){line tmp;tmp.k=k,tmp.b=b;return tmp;}
struct li_chao_segment_tree_in_a_BIT{
line val[maxn*100];
int cnt,rt[330],ls[maxn*100],rs[maxn*100];
void ins(int &idx,int l,int r,line L){
if(!idx){idx=++cnt;val[idx]=L;return;}
int mid=(l+r)>>1;
if(val[idx].get(mid)<L.get(mid))swap(val[idx],L);
if(val[idx].get(l)<L.get(l))ins(ls[idx],l,mid,L);
if(val[idx].get(r)<L.get(r))ins(rs[idx],mid+1,r,L);
}
ll query(int idx,int l,int r,int x){
if(!idx)return 0;
ll res=val[idx].get(x);
if(l==r)return res;
int mid=(l+r)>>1;
return max(res,(x<=mid)?query(ls[idx],l,mid,x):query(rs[idx],mid+1,r,x));
}
void ins(int loc,line L){
for(int i=loc;i<=m;i+=i&(-i))ins(rt[i],1,n+m,L);
}
ll query(int loc,int x){
ll ans=-inf;
for(int i=loc;i;i-=i&(-i))ans=max(ans,query(rt[i],1,n+m,x));
return ans;
}
}t;
ll dp[maxn];
ll g(int i,int j){return dp[get_id(i,j)]-1ll*buff[get_id(i,j)]*(i+j);}
int main(){
scanf("%d%d",&n,&m);
rep(i,1,n)rep(j,1,m)scanf("%d",&buff[get_id(i,j)]);
rep(i,1,n)rep(j,1,m)scanf("%d",&val[get_id(i,j)]);
if(n<m){//m作为树状数组的维度 应该尽量小
rep(i,1,m)rep(j,1,n)bk1[get_id(i,j,n)]=buff[get_id(j,i)],bk2[get_id(i,j,n)]=val[get_id(j,i)];
swap(n,m);rep(i,1,n*m)buff[i]=bk1[i],val[i]=bk2[i];
}
memset(dp,-0x3f,sizeof(dp));
dp[get_id(1,1)]=0;t.ins(1,mk_l(buff[get_id(1,1)],g(1,1)));
rep(i,1,n)rep(j,1,m)if(i!=1||j!=1){
int idx=get_id(i,j);
dp[idx]=t.query(j,i+j)+val[idx];
t.ins(j,mk_l(buff[idx],g(i,j)));
}
cout<<dp[get_id(n,m)];
return 0;
}