Growth

题意

有两个属性和，每一天他可以通过努力，让涨点或涨点。

有种奖励，当大于等于，大于等于时，每天可以获得的奖励。

问天可以获得的最大奖励是多少？

分析

首先我们将和分别离散化。

然后我们可以定义表示第天可以获得的总奖励。

表示第天当天可以获得的总奖励。

转移方程

可以通过二维前缀和求解出来。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 1110;
const int M = 1e9+7;
int n,m,t,k;

int dp[maxn][maxn],a[maxn][maxn];

int b[maxn],c[maxn],d[maxn];        //原数据

int x[maxn],y[maxn];        //离散数组

signed main()
{
    cin>>t>>k;
    for(int i = 1; i <= t; i++) 
    {
        cin>>b[i]>>c[i]>>d[i];
        x[i] = b[i];
        y[i] = c[i];
    }
    sort(x+1,x+1+t);
    sort(y+1,y+1+t);
    n = unique(x+1,x+1+t)-x-1;
    m = unique(y+1,y+1+t)-y-1;      //离散化
    for(int i = 1; i <= t; i++) 
    {
        b[i] = lower_bound(x+1,x+1+n,b[i])-x;
        c[i] = lower_bound(y+1,y+1+m,c[i])-y;
        a[b[i]][c[i]] += d[i];
    }
    for(int i = 1; i <= n; i++) 
    {
        for(int j = 1; j <= m; j++) 
        {
            a[i][j] += a[i-1][j]+a[i][j-1]-a[i-1][j-1];         //二维前缀和
        }
    }
    for(int i = 1; i <= n; i++)                 //dp
    {
        for(int j = 1; j <= m; j++) 
        {
            dp[i][j] = max(dp[i-1][j]+(x[i]-x[i-1]-1)*a[i-1][j],dp[i][j-1]+(y[j]-y[j-1]-1)*a[i][j-1]) + a[i][j];
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) 
    {
        for(int j = 1; j <= m; j++) 
        {   
            if(x[i] + y[j] > k) break;
            ans = max(ans,dp[i][j]+(k-x[i]-y[j])*a[i][j]);      //枚举答案
        }
    }
    cout<<ans<<endl;
    return 0;
}