2020牛客NOIP赛前集训营-提高组（第一场） D题 题解

本场全部题解见此

更好的阅读体验

D 牛牛的RPG游戏

题外话：这几天在刷dp优化，刚好做了斜率优化（李超线段树）和cdq分治优化dp

题意简述

有一个 的网格，要从 走到 ，规定只能向下或向右走。

当走到一个格子，你可以选择是否触发事件，一个格子 上的事件用 和 表示。

触发事件后，你的得分立即加上 ，同时你的属性值立即变成 ，

每走一步，你的得分都要加上当前身上的属性值。初始得分和属性值都是 。

求走到 时的最大得分。

数据保证 。

。

算法标签

dp 斜率优化 李超线段树 cdq分治

算法分析

暴力的 dp 不难写出。设 表示走到 并触发事件，触发事件前的最大得分，则：

于是你得了20分。

考虑优化这个方程，发现方程有乘积项，考虑化成斜率优化的形式。

其实上面的式子并不是维护凸包的斜率优化式子，因为我不会决策点不单调的动态维护凸包……

令：

• 
• 
• 
• 

  仅和 有关 ， 仅和 有关，可以将决策点 看做 的直线， 处dp的最优值即为 与所有决策点代表直线的最大值。

这样就可以直接上李超线段树了，这可以解决 的部分分，稍微处理一下可以解决 的部分分。

现在还有一个问题，就是决策点集合的问题。

所有的决策点可以看做二维平面上的点，而一个点的决策点集合是二维偏序。

二维偏序考虑 cdq 分治，对行 cdq 分治，然后对列做斜率优化dp ,时间复杂度为 。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
#define maxm 10000005
#define inf 0x3f3f3f3f3f3f3f3fll
#define int long long
#define mod 1000000007
#define local
void file(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
template <typename Tp>void read(Tp &x){
    x=0;int fh=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-'){fh=-1;}c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=fh;
}
int n,m;
vector<int>buff[maxn],val[maxn],dp[maxn];
namespace LiChaoTree{
    #define eps 1e-8
    struct Seg{int k,b;}a[maxn];
    int calc(Seg sg,int x){return sg.k*x+sg.b;}
    int dcmp(double x){return fabs(x)<=eps?0:(x>0?1:-1);}
    #define mid ((l+r)>>1)
    int tag[maxm],lson[maxm],rson[maxm],tot=1;
    int cnt;
    int upd(int x,int l,int r,int id){
        if(!x){
            x=++tot;
            tag[x]=lson[x]=rson[x]=0;
        }
        if(!tag[x]||calc(a[tag[x]],mid)<calc(a[id],mid))swap(id,tag[x]);
        if(l==r||a[tag[x]].k==a[id].k||!id)return x;
        double isc=(a[tag[x]].b-a[id].b)*1.0/(a[id].k-a[tag[x]].k);
        if(dcmp(isc-l)<0||dcmp(isc-r)>0)return x;
        if(dcmp(isc-mid)==0){
            if(calc(a[tag[x]],l)>calc(a[id],l))rson[x]=upd(rson[x],mid+1,r,id);
            else lson[x]=upd(lson[x],l,mid,id);
            return x;
        }
        if(dcmp(isc-mid)<0)lson[x]=upd(lson[x],l,mid,id);
        else rson[x]=upd(rson[x],mid+1,r,id);
        return x;
    }
    int query(int x,int l,int r,int p){
        if(!x)return -inf;
        if(l==r)return calc(a[tag[x]],p);
        int ret=calc(a[tag[x]],p);
        if(p<=mid)ret=max(ret,query(lson[x],l,mid,p));
        else ret=max(ret,query(rson[x],mid+1,r,p));
        return ret;
    }
    void reset(){
        a[0]=(Seg){0,-inf};
        cnt=0;tot=1;
        tag[1]=lson[1]=rson[1]=0;
    }
    void insert(int k,int b){
        a[++cnt]=(Seg){k,b};
        upd(1,0,200000,cnt);
    }
    int ask(int x){
        return query(1,0,200000,x);
    }
    #undef mid
}
void solve(int l,int r){
    if(l==r){
        LiChaoTree::reset();
        if(l==0)dp[0][0]=0;
        LiChaoTree::insert(buff[l][0],dp[l][0]+val[l][0]);
        for(int i=1;i<m;++i){
            dp[l][i]=max(dp[l][i],LiChaoTree::ask(i));
            LiChaoTree::insert(buff[l][i],dp[l][i]+val[l][i]-i*buff[l][i]);
        }
        return;
    }
    int mid=((l+r)>>1);
    solve(l,mid);

    LiChaoTree::reset();
    for(int j=0;j<m;++j){
        for(int i=l;i<=mid;++i){
            LiChaoTree::insert(buff[i][j],-(i+j)*buff[i][j]+val[i][j]+dp[i][j]);
        }
        for(int i=mid+1;i<=r;++i){
            dp[i][j]=max(dp[i][j],LiChaoTree::ask(i+j));
        }
    }
    solve(mid+1,r);
}

signed main(){
    read(n);read(m);
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            buff[i].push_back(0);
            val[i].push_back(0);
            dp[i].push_back(-inf);
        }
    }
    for(int i=0;i<n;++i)for(int j=0;j<m;++j)read(buff[i][j]);
    for(int i=0;i<n;++i)for(int j=0;j<m;++j)read(val[i][j]);
    solve(0,n-1);
    printf("%lld\n",dp[n-1][m-1]);
    return 0;
}