每日一题 6月30日 Growth 离散化+DP

题目链接：https://ac.nowcoder.com/acm/problem/19809
题目大意：

思路：

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

LL x[1005], y[1005], z[1005];
LL a[1005], b[1005], c[1005];
LL s[1005][1005], f[1005][1005], s1[1005][1005], s2[1005][1005];
int main(){

    int n, m; scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++){
        scanf("%lld%lld%lld", &x[i], &y[i], &z[i]);
        a[i]=x[i], b[i]=y[i];
    }
    sort(a+1, a+n+1); sort(b+1, b+n+1);
    int cnt1=unique(a+1, a+n+1)-a-1;
    int cnt2=unique(b+1, b+n+1)-b-1;
    for(int i=1; i<=n; i++){
        x[i]=lower_bound(a+1, a+cnt1+1, x[i])-a;
        y[i]=lower_bound(b+1, b+cnt2+1, y[i])-b;
        s[x[i]][y[i]]+=z[i];
    }
    for(int i=1; i<=cnt1; i++){
        for(int j=1; j<=cnt2; j++){
            s1[i][j]=s1[i][j-1]+s[i][j];
        }
    }
    for(int j=1; j<=cnt2; j++){
        for(int i=1; i<=cnt1; i++){
            s2[i][j]=s2[i-1][j]+s[i][j];
        }
    }
    LL ans=0;
    for(int i=1; i<=cnt1; i++){
        for(int j=1; j<=cnt2; j++){
            if(a[i]+b[j]<=m){
                f[i][j]=max(f[i-1][j]+s1[i][j]*(m-a[i]-b[j]+1), f[i][j-1]+s2[i][j]*(m-a[i]-b[j]+1));
            }
            ans=max(ans, f[i][j]);
        }
    }
    printf("%lld\n", ans);

    return 0;
}