一道有意思的dp(2018牛客国庆集训派对Day6)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1004;
ll X[maxn],Y[maxn],n,m,v[maxn][maxn],t[maxn][maxn],dp[maxn][maxn];
struct Node {
    ll x,y,z;
}pp[maxn];
int main()
{
    scanf("%lld%lld",&n,&m);    
    ll cnt=0,numx,numy,x,y,z;
    for(ll i=1;i<=n;i++) {
        scanf("%lld%lld%lld",&x,&y,&z);
        if(x+y>m) continue;
        pp[++cnt].x=x;
        pp[cnt].y=y,pp[cnt].z=z,X[cnt]=x,Y[cnt]=y;
    }
    sort(X+1,X+1+cnt); sort(Y+1,Y+1+cnt);
    numx=unique(X+1,X+1+cnt)-X-1;
    numy=unique(Y+1,Y+1+cnt)-Y-1;
    for(ll i=1;i<=n;i++) {
        ll r=lower_bound(X+1,X+1+numx,pp[i].x)-X,c=lower_bound(Y+1,Y+1+numy,pp[i].y)-Y; 
        t[r][c]+=pp[i].z; //+=而不是=因为可能有重复数据 
    }
    for(ll i=1;i<=numx;i++) for(ll j=1;j<=numy;j++) v[i][j]=v[i-1][j]+v[i][j-1]-v[i-1][j-1]+t[i][j];
    for(ll i=1;i<=numx;i++) for(ll j=1;j<=numy;j++) 
        dp[i][j]=v[i][j]+max(dp[i-1][j]+v[i-1][j]*(X[i]-X[i-1]-1),dp[i][j-1]+v[i][j-1]*(Y[j]-Y[j-1]-1));
    ll ans=0;
    for(ll i=1;i<=numx;i++) for(ll j=1;j<=numy;j++) 
        if(X[i]+Y[j]<=m) ans=max(ans,dp[i][j]+v[i][j]*(m-X[i]-Y[j])); 
    printf("%lld",ans);
    return 0;
}