每日一题 6.30 Growth

本来以为是一道二维前缀和的问题 但写了一会在看看题不会（当场死亡qwq
摸鱼思考了亿会 还是看了题解
要离散化+dp+二维前缀和 我写下我的一丝丝理解
对数据进行离散化 将数量大小转化为数组坐标大小 天数的变化就是以X[i]和Y[i]来了
v[i][j] 表示 第 X[i]+Y[j] 天能得到的分数值
dp[i][j]表示X[i]+Y[j]天能得到的最大分数
代码要详细注释

 #include<bits/stdc++.h>
#define ll long long
using namespace std;
int const N=1005;
ll n,m,X[N],Y[N],cnt1,cnt2,cnt,x,y,z,v[N][N],dp[N][N],ans;
struct T
{
    ll x,y,z;
}a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        cin>>x>>y>>z;
        if(x+y>m) continue;
        a[++cnt].x=x;a[cnt].y=y;a[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 xx=lower_bound(X+1,X+1+cnt1,a[i].x)-X;
        int yy=lower_bound(Y+1,Y+1+cnt2,a[i].y)-Y;
        v[xx][yy]+=a[i].z;
    }
    for(int i=1;i<=cnt1;++i)
        for(int j=1;j<=cnt2;++j)///v[i][j] 表示 第 X[i]+Y[j] 天能得到的分数值
        v[i][j]+=v[i-1][j]+v[i][j-1]-v[i-1][j-1];///二维前缀和
    for(int i=1;i<=cnt1;++i)///是加a还是加b  选择能得值最大的
        for(int j=1;j<=cnt2;++j)///dp[i][j]表示X[i]+Y[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]);
        ///X[i]-X[i-1]-1 表示每天增加v[i-1][j]的总天数
    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;
}