Growth(后续效益持续作用，离散化dp)

题：https://ac.nowcoder.com/acm/problem/19809

题意：俩个属性ai，bi，每天可以选择任选一个属性加1，有n件物品属性：xi，yi，zi，当属性ai>=xi&&bi>=yi,在接下来的每天中都会获得zi的收益，问在m天中最多能收益多少（m<=2e8,xi,y1<=1e8,n<=1e3）

分析：

先离散化；
定义dp[i][j] 为属性ai到达i，bj到达 j 时能够获得的最大代价；
定义val[i][j]为属性ai到达i，bj到达 j 时能够获得的代价和（记1天的代价）；
那么dp[i][j]可以由dp[i-1][j], dp[i][j-1]转化来，前者相差X[i]-X[i-1]-1天，也就是得到了（X[i]-X[i-1]-1）倍dp[i][j-1]的效益，同时加上一倍的val [i][j],后者也同理；
最后更新答案，后面的m-X[i]-Y[j]有得“白嫖”；

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int inf=0x3f3f3f3f;
const ll INF=(1ll<<40);
const int M=1e3+6;
struct node{
    ll x,y,z;
}a[M];
ll val[M][M],dp[M][M];
ll X[M],Y[M];
int tot;
int main(){
    int n;
    ll m;
    scanf("%d%lld",&n,&m);
    for(int i=1;i<=n;i++){
        ll x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        if(x+y>m)
            continue;
        a[++tot].x=x;
        a[tot].y=y;
        a[tot].z=z;
        X[tot]=x;
        Y[tot]=y;
    }
    sort(X+1,X+1+tot);
    int totA=unique(X+1,X+1+tot)-X-1;
    sort(Y+1,Y+1+tot);
    int totB=unique(Y+1,Y+1+tot)-Y-1;
    for(int i=1;i<=n;i++){
        int pos1=lower_bound(X+1,X+1+totA,a[i].x)-X;
        int pos2=lower_bound(Y+1,Y+1+totB,a[i].y)-Y;
        val[pos1][pos2]+=a[i].z;
    }
    for(int i=1;i<=totA;i++)
        for(int j=1;j<=totB;j++)
            val[i][j]+=val[i-1][j]+val[i][j-1]-val[i-1][j-1];
    for(int i=1;i<=totA;i++)
        for(int j=1;j<=totB;j++){
            dp[i][j]=val[i][j]+max(dp[i-1][j]+(X[i]-X[i-1]-1)*val[i-1][j],dp[i][j-1]+(Y[j]-Y[j-1]-1)*val[i][j-1]);
        }
    ll ans=0;
    for(int i=1;i<=totA;i++)
        for(int j=1;j<=totB;j++)
            if(X[i]+Y[j]<=m)
                ans=max(ans,(m-X[i]-Y[j])*val[i][j]+dp[i][j]);
    printf("%lld
",ans);
    return 0;
}

View Code

定义dp[i][j] 为属性ai到达