NEUQ OJ - 2057 Growth（DP，离散化处理）

题目链接：NEUQ OJ - 2057 Growth

分析：

明显需要用DP，但是发现DP前需要先得到 a=i b=j 时的达到条件的z之和，才能算出 这一天分数加了多少，记作 s[i][j] ，则有：
$$s[i][j]=s[i?1][j]+s[i][j?1]?s[i?1][j?1]+z[i][j]$$
其中减去 s[i-1][j-1] 是因为 s[i-1][j] 和 s[i][j-1] 中均包含了 s[i-1][j-1] ，因此减去重复的一个

那么就可以得到DP的状态转移方程：
d p [ i ] [ j ] = m a x { d p [ i ? 1 ] [ j ] , d p [ i ] [ j ? 1 ] } + s [ i ] [ j ] dp[i][j] = max\left \{ dp[i-1][j], dp[i][j-1]\right \}+s[i][j] dp[i][j]=max{ dp[i?1][j],dp[i][j?1]}+s[i][j]
其中 dp[i][j] 代表当 a=i b=j 时得到的最大分数

因为题目要求求出m天时候的最大分数，那么最终结果还应当加上 (m - i - j) * s[i][j]

但是因为x_i和y_i比较大，所以要对其进行离散化处理，同时DP状态转移方程会发生改变，详见代码。

以下代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e3+50;
int n,m;
LL x[maxn],y[maxn],z[maxn];
LL X[maxn],Y[maxn],Z[maxn][maxn];
LL s[maxn][maxn],dp[maxn][maxn];
int main()
{
    scanf("%d %d",&n,&m);for(int i=1;i<=n;i++){
    scanf("%lld %lld %lld",&x[i],&y[i],&z[i]);X[i]=x[i];Y[i]=y[i];}//接下来继续离散化处理sort(X+1,X+n+1);int nx=unique(X+1,X+n+1)-(X+1);sort(Y+1,Y+n+1);int ny=unique(Y+1,Y+n+1)-(Y+1);memset(Z,0,sizeof(Z));for(int i=1;i<=n;i++){
    int tx=lower_bound(X+1,X+nx+1,x[i])-X;    //找到x[i]的映射int ty=lower_bound(Y+1,Y+ny+1,y[i])-Y;    //找到y[i]的映射Z[tx][ty]+=z[i];      //确定映射后的z[i][j]}memset(s,0,sizeof(s));for(int i=1;i<=nx;i++)for(int j=1;j<=ny;j++)s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+Z[i][j];memset(dp,0,sizeof(dp));for(int i=1;i<=nx;i++){
    for(int j=1;j<=ny;j++){
    LL t1=dp[i-1][j]+(X[i]-X[i-1]-1)*s[i-1][j];     //(X[i]-X[i-1]-1)表示i-1到i中间跨越的天数//然后乘上s[i-1][j]LL t2=dp[i][j-1]+(Y[j]-Y[j-1]-1)*s[i][j-1];     //(Y[j]-Y[j-1]-1)表示j-1到j中间跨越的天数//然后乘上s[i][j-1]dp[i][j]=max(t1,t2)+s[i][j];      //取最大的，再加上当天获得的分数}}LL ans=0;for(int i=1;i<=nx;i++)for(int j=1;j<=ny;j++)ans=max(ans,dp[i][j]+(m-X[i]-Y[j])*s[i][j]);    //(m-X[i]-Y[j])表示剩余的天数，然后乘上s[i][j]printf("%lld\n",ans);return 0;
}