Growth

题意:a,b两个属性,每天可以+1点a,或者+1点b,然后当a>xi并且b>yi,可以获得zi的奖励,之后的每天都可以获得zi的奖励,现在来求zi最大是多少
题解:离散化dp
我们先假设xi和yi,m比较小,那么先求v[i][j],表示在a=i,b=j时在剩下的天数里即(m-i-j)天里每天可以获得的zi值
也就是


相当于求的是从第一天起,到a加了i点,b加了j点,时可以获得的全部的zi值
那么对于最后答案就是


即,求a=i和b=j时状态,可以由两个状态得到,即i-1,j和i,j-1状态,然后这两个状态取最大加上v[i][j],就是到a=i,b=j时的所获得的zi值
然后因为有m天,所以要再求下ans
时间复杂度:
然后还没完,刚一半
这个题给的m,xi,yi都比较大,然后下来用到离散化

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：
原数据：1,999,100000,15；处理后：1,3,4,2；
原数据：{100,200}，{20,50000}，{1,400}；
处理后：{3,4}，{2,6}，{1,5}；---来自百度百科

然后对于离散的方法就是,排序,去重
sort和unique
先通过记录下每个数字,然后对其进行排序和去重,一定要先排序
排序之后的数字所对应的下标,就是我们的新的i和j

 for(int i=1;i<=n;i++){ 
        scanf("%d%d%d",&x,&y,&z);
        if(x+y>m)continue;
        p[++cnt].x=x;
        p[cnt].y=y;
        p[cnt].z=z;
        X[++cnt1]=x;
        Y[++cnt2]=y;
    }
    sort(X+1,X+1+cnt1); 
    cnt1=unique(X+1,X+1+cnt1)-X-1;
    sort(Y+1,Y+1+cnt2);
    cnt2=unique(Y+1,Y+1+cnt2)-Y-1;
    for(int i = 1; i <= n; i++) {
        int cn = lower_bound(X+1,X+1+cnt1,p[i].x) -X;
        int cy = lower_bound(Y+1,Y+1+cnt2,p[i].y) -Y;
        v[cn][cy] +=p[i].z;
    }

以上操作就相当于把很大的数字转化为较小的数字,也就是数组可以开的下的大小,和运算次数可以过的数量级
那么到此就把数字比较大的问题解决,所以就会到上面的状态转移式子
总结就是那一个数组的下标来代替一个比较大的数字
但是到此出现问题就是求a=i和b=j时,可以由两个状态得到,即i-1,j和i,j-1状态,上面的数字比较小的话那么i和i-1的差值为1,那么就不存在这个问题,但是现在的问题就是i和i-1的状态的差值不为1,状态之间相差
所以dp转移式子变成

状态转移相差的天数要加上相应的v[i][j]
然后ans的也发生相应的变化

离散化相当与预处理:
时间复杂度为:
然后对于离散化的题的时间复杂度都是假的..........具体要看离散化的程度,以上时间复杂度仅供参考

#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
#define maxx 1005
using namespace std;
struct  node
{
    int x,y,z;
}p[maxx]; 
long long  X[maxx]; 
long long  Y[maxx];
long long v[maxx][maxx]; 
long long dp[maxx][maxx]; 
int cnt1,cnt2,cnt; 
int main()
{
    int n,m;
    cin>>n>>m;
    int x,y,z;
    for(int i=1;i<=n;i++){ 
        scanf("%d%d%d",&x,&y,&z);
        if(x+y>m)continue;
        p[++cnt].x=x;
        p[cnt].y=y;
        p[cnt].z=z;
        X[++cnt1]=x;
        Y[++cnt2]=y;
    }
    sort(X+1,X+1+cnt1); 
    cnt1=unique(X+1,X+1+cnt1)-X-1;
    sort(Y+1,Y+1+cnt2);
    cnt2=unique(Y+1,Y+1+cnt2)-Y-1;
    for(int i = 1; i <= n; i++) {
        int cn = lower_bound(X+1,X+1+cnt1,p[i].x) -X;
        int cy = lower_bound(Y+1,Y+1+cnt2,p[i].y) -Y;
        v[cn][cy] +=p[i].z;
    }
    for(int i=1;i<=cnt1;i++)
    for(int j=1;j<=cnt2;j++)
        v[i][j]+=v[i-1][j]+v[i][j-1]-v[i-1][j-1];
    for(int i=1;i<=cnt1;i++)
    for(int j=1;j<=cnt2;j++)
        dp[i][j]=v[i][j]+max(dp[i-1][j]+(X[i]-X[i-1]-1)*v[i-1][j],dp[i][j-1]+(Y[j]-Y[j-1]-1)*v[i][j-1]);
    long long ans=0;
    for(int i=1;i<=cnt1;i++)
    for(int j=1;j<=cnt2;j++)
        if(X[i]+Y[j]<=m)ans=max(ans,dp[i][j]+(m-X[i]-Y[j])*v[i][j]);

    cout<<ans<<endl;
    return 0;
}