题解 AT_joisc2019_e - ふたつの料理

· · 题解

把一个方案转化为从 (0,0) 到 (n,m) 的一条折线（每次向右或向上），而题目所给的每个信息可以转化为在例如第一道菜第 i 个步骤结束前第二道菜至多进行了 j 个步骤就可以获得若干贡献。然后可以转化为有若干个点有权值，最终的满意度就是折线下方的点的权值之和（上方的条件可以先加到答案，然后建立相反数作权值的点）。

一个朴素的动态规划是 f_{i,j} 表示第一道菜做了 i 步，第二道菜做了 j 步的最大满意度。

把 i 从 1 到 n 进行转移，维护每个 j 的上的状态的值。这时若从 (i-1,j) 转移到 (i,j)，就增加了第 i 列下 j 格中点的权值和；若从 (i,j-1) 转移到 (i,j)，状态值则不会发生改变。

于是问题转化为维护一个数列，要支持后缀加一个数或后缀取 \max。

考虑对这个数列做差分，所有非 0 的差分项放入一个 map 中，每次加一个数 x 之后立即后缀取 \max。

原序列后缀取 \max 就等价于在差分数组上找到负值变为 0 后向后调整。在这里需要每次拉出一个数 y 来与 x 相加，并把 y 变为 0。

时间复杂度 \Theta((n+m)\log\min(n,m))。

#include<bits/stdc++.h>
using namespace std;

int n,m;
long long a[1000001],b[1000001];
long long s[1000001],t[1000001];
int p[1000001],q[1000001];
vector<pair<int,long long> > vec[1000001];
map<int,long long> diff;

inline bool cmp(pair<int,long long> x,pair<int,long long> y){
    return x.second>y.second;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld%d",a+i,s+i,p+i),a[i]+=a[i-1];
    for(int i=1;i<=m;i++)
        scanf("%lld%lld%d",b+i,t+i,q+i),b[i]+=b[i-1];
    long long answer=0;
    for(int i=1;i<=n;i++){
        if(s[i]<a[i])continue;
        int pos=upper_bound(b+1,b+1+m,s[i]-a[i])-b,v=p[i];
        answer+=v; if(1<=pos&&pos<=m)vec[i].push_back({pos,-v});
    }
    for(int i=1;i<=m;i++){
        if(t[i]<b[i])continue;
        int pos=upper_bound(a+1,a+1+n,t[i]-b[i])-a,v=q[i];
        if(1<=pos&&pos<=n)vec[pos].push_back({i,v});
        else answer+=v;
    }
    diff[m+1]=1ll<<62;
    for(int i=1;i<=n;i++){
        sort(vec[i].begin(),vec[i].end(),cmp);
        for(pair<int,long long> j :vec[i]){
            auto it=diff.lower_bound(j.first);
            int x=j.first; long long v=j.second;
            while(v<0&&it!=diff.end()){
                x=(*it).first,v+=(*it).second;
                it=diff.erase(it);
            }
            diff[x]=diff[x]+v;
        }
    }
    for(pair<int,long long> v :diff)
        if(1<=v.first&&v.first<=m)answer+=v.second;
    printf("%lld\n",answer);
    return 0;
}