[二维平面离散点的DP][离散化] 2018camp day1 Growth

http://newoj.acmclub.cn/problems/2057

看的时候没有什么思路，想过dp但是感觉数据量不可行，看了题解才意识到离散化即可O(n^2)，暴力刷表推出来每个点的最优值即可。

此外，还学习到了v[i][j]=v[i][j-1]+v[i-1][j]-v[i-1][j-1]+mp[make_pair(x[i],y[j])];这种处理方法，如果没有想到-v[i-1][j-1]的话，就不会想到推出来vij也就没有后面的操作了。此外，在二维平面上这种只有两个轴向转移的思想也是很重要。确定了dp的一个转移的方向。最后，确定答案的一步也很有趣，由于离散化导致的不能确定m天的位置，所以只能再遍历所有的点然后取小于等于m天的那些点向m天转移的最大值。

wa点的话离散化忘记去重。。。。很尴尬的操作

#include

using namespace std;

typedef long long LL;
const int maxn=1e3+5;
const int mod=1e9+7;

LL v[maxn][maxn],dp[maxn][maxn],x[maxn],y[maxn];
map,LL > mp;

int main()
{
    LL n,m,z;
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        scanf("%lld %lld %lld",&x[i],&y[i],&z);
        mp[make_pair(x[i],y[i])]+=z;
    }
    sort(x+1,x+1+n);
    sort(y+1,y+1+n);
    int cx=1,cy=1;
    for (int i=2;i<=n;i++)//error3
    {
        if(x[cx]!=x[i])
            x[++cx]=x[i];
        if(y[cy]!=y[i])
            y[++cy]=y[i];
    }

    for (int i=1;i<=cx;i++)
        for (int j=1;j<=cy;j++)
        v[i][j]=v[i][j-1]+v[i-1][j]-v[i-1][j-1]+mp[make_pair(x[i],y[j])];

    for (int i=0;i<=cx;i++)
        for (int j=0;j<=cy;j++)
    {
        dp[i+1][j]=max(dp[i+1][j],dp[i][j]+v[i][j]*(x[i+1]-x[i]-1)+v[i+1][j]);//error1+error2
        dp[i][j+1]=max(dp[i][j+1],dp[i][j]+v[i][j]*(y[j+1]-y[j]-1)+v[i][j+1]);
    }
    LL ans=0;
    for(int i=1;i<=cx;i++)
        for (int j=1;j<=cy;j++)
    {
        if(x[i]+y[j]<=m)
        {
            ans=max(ans,dp[i][j]+v[i][j]*(m-x[i]-y[j]));
        }
    }
    cout<