欢迎访问个人博客

传送门 $\looparrowright$

题目描述

  弱弱有两个属性 $a$ 和 $b$，这两个属性初始的时候均为 $0$，每一天他可以通过努力，让 $a$ 涨 $1$ 点或 $b$ 涨 $1$点。   为了激励弱弱努力学习，我们共有 $n$ 种奖励，第 $i$ 种奖励有 $x_i,y_i,z_i$ 三种属性，若 $a\ge x_i$ 且 $b\ge y_i$，则弱弱在接下来的每一天都可以得到 $z_i$ 的分数。 问 $m$ 天以后弱弱最多能得到多少分数。

输入描述

  第一行一个两个整数 $n$ 和 $m$$(1\le n\le 1000,1\le m\le 2000000000)$。   接下来 $n$ 行，每行三个整数 $x_i,y_i,z_i$$(1\le x_i,y_i\le 1000000000,1\le z_i\le 1000000)$。

输出描述

  一行一个整数表示答案。

示例1

输入 2 4 2 1 10 1 2 20 输出 50

备注

  在样例中，弱弱可以这样规划：第一天 $a$ 涨 $1$，第二天 $b$ 涨 $1$，第三天 $b$ 涨 $1$，第四天 $a$ 涨 $1$。   共获得 $0+0+20+30=50$ 分。

分析

  定义 $v[i][j]$，为保持 $a=i，b=j$ 的状态，在将来 $m-i-j$ 天，每天能获得的分数。定义 $dp[i][j]$ 表示，当恰好达到 $a=i,b=j$ 的状态时，能够获得的最高分。   初始状态为 $v[x_i][y_i]=z_i$，类似二维前缀和，递推可得，v[i][j]+=v[i-1][j]+v[i][j-1]-v[i-1][j-1]。   有状态转移方程，$dp[i][j]=v[i][j]+\max (dp[i-1][j],dp[i][j-1])$。   此题 $x_i,y_i$ 的数据较大，因此需要进行离散化。定义两个数组 $X,Y$，对 $x_i,y_i$ 离散化。因此 $v[i][j]$ 表示，保持 $a=X[i],b=Y[j]$ 的状态，在将来 $m-i-j$ 天，每天能获得的分数；$dp[i][j]$ 表示，当恰好达到 $a=X[i],b=Y[j]$ 的状态时，能够获得的最高分。   状态转移方程为 $dp[i][j]=v[i][j]+\max (dp[i-1][j]+(X[i]-X[i-1]-1)\times v[i-1][j],dp[i][j-1]+(Y[j]-Y[j-1]-1)\times v[i][j-1])$，从 $X[i-1]$ 过渡到 $X[i]$，有 $X[i]-X[i-1]-1$ 天获得的分数为 $v[i-1][j]$；从 $Y[j-1]$ 过渡到 $Y[j]$ 同理。   假设 $m$ 天结束后的状态为 $a=X[i],b=Y[j]$，则获得的最高分为，$dp[i][j]+v[i][j]\times (m-X[i]-Y[i])$。因此可以枚举结束后的状态 $i,j$ 得到答案，即 $ans=\underset{1\le i\le cx,1\le j\le cy}{\max }dp[i][j]+v[i][j]\times (m-X[i]-Y[i])$，其中 $cx$ 为不同的 $x_i$ 的个数，$cy$ 为不同的 $y_i$ 的个数。

代码

#include<iostream> #include<algorithm> #include<cstdio> #define N 1002 #define ll long long using namespace std; //-------------- //n为奖励的个数。 //m为经历的天数。 int n,m; //-------------- //----------------------------------------------------------------- //X,Y为离散化数组。 //v[i][j]表示，保持a=X[i]，b=Y[j]的状态，在将来(m-X[i]-Y[j])天，每天能获得的分数。 //dp[i][j]表示，当a=X[i]，b=Y[j]时，能够获得的最高分。 ll X[N],Y[N]; ll v[N][N]; ll dp[N][N]; //----------------------------------------------------------------- //-------------------------------------------------- //reward数组记录奖励的信息，其中x+y>m的奖励不必要记录。 //cnt为可行奖励的个数（对于其中任意一条奖励，有x+y<=m）。 //cx为X离散化后的大小 //cy为Y离散化后的大小 struct node { ll x; ll y; ll z; }reward[N]; int cnt,cx,cy; //-------------------------------------------------- int main() { cin>>n>>m; int i,j; for(i=1;i<=n;i++) { ll x,y,z; scanf("%lld%lld%lld",&x,&y,&z); if(x+y>m) continue;//忽略 reward[++cnt]=node{x,y,z}; X[++cx]=x; Y[++cy]=y; } //------------------------------- //排序，去重。 sort(X+1,X+1+cx); cx=unique(X+1,X+1+cx)-X-1; sort(Y+1,Y+1+cy); cy=unique(Y+1,Y+1+cy)-Y-1; //------------------------------- //----------------------------------------------- //初始化。 for(i=1;i<=n;i++) { int I=lower_bound(X+1,X+1+cx,reward[i].x)-X; int J=lower_bound(Y+1,Y+1+cy,reward[i].y)-Y; v[I][J]+=reward[i].z;//注意"+=" } //------------------------------------------------ //------------------------------------------------ //二维前缀和维护v[i][j] for(i=1;i<=cx;i++) { for(j=1;j<=cy;j++) { v[i][j]+=v[i-1][j]+v[i][j-1]-v[i-1][j-1]; } } //------------------------------------------------ //------------------------------------------------------------------------------------------------------- //递推dp[i][j]。 for(i=1;i<=cx;i++) { for(j=1;j<=cy;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]); } } //-------------------------------------------------------------------------------------------------------- //--------------------------------------------------------- //假设最终状态为a=X[i],b=Y[j]，更新答案。 ll ans=0; for(i=1;i<=cx;i++) { for(j=1;j<=cy;j++) { if(X[i]+Y[j]>m) continue; ans=max(ans,dp[i][j]+(ll)(m-X[i]-Y[j])*v[i][j]); } } //--------------------------------------------------------- cout<<ans<<endl; return 0; }