题目描述
弱弱有两个属性 a a a 和 b b b ,这两个属性初始的时候均为 0 0 0 ,每一天他可以通过努力,让 a a a 涨 1 1 1 点或 b b b 涨 1 1 1 点。
为了激励弱弱努力学习,我们共有 n n n 种奖励,第 i i i 种奖励有 x i , y i , z i x_i,y_i,z_i x i , y i , z i 三种属性,若 a ≥ x i a≥ x_i a ≥ x i 且 b ≥ y i b≥ y_i b ≥ y i ,则弱弱在接下来的每一天都可以得到 z i z_i z i 的分数。
问 m m m 天以后弱弱最多能得到多少分数。
输入描述
第一行一个两个整数 n n n 和 m m m ( 1 ≤ n ≤ 1000 , 1 ≤ m ≤ 2000000000 ) (1≤ n≤ 1000,1≤ m≤ 2000000000) ( 1 ≤ n ≤ 1000 , 1 ≤ m ≤ 2000000000 ) 。
接下来 n n n 行,每行三个整数 x i , y i , z i x_i,y_i,z_i x i , y i , z i ( 1 ≤ x i , y i ≤ 1000000000 , 1 ≤ z i ≤ 1000000 ) (1≤ x_i,y_i≤ 1000000000,1≤ z_i ≤ 1000000) ( 1 ≤ x i , y i ≤ 1000000000 , 1 ≤ z i ≤ 1000000 ) 。
输出描述
一行一个整数表示答案。
示例1
输入
2 4
2 1 10
1 2 20
输出
50
备注
在样例中,弱弱可以这样规划:第一天 a a a 涨 1 1 1 ,第二天 b b b 涨 1 1 1 ,第三天 b b b 涨 1 1 1 ,第四天 a a a 涨 1 1 1 。
共获得 0 + 0 + 20 + 30 = 50 0+0+20+30=50 0 + 0 + 20 + 30 = 50 分。
分析
定义 v [ i ] [ j ] v[i][j] v [ i ] [ j ] ,为保持 a = i , b = j a=i,b=j a = i , b = j 的状态,在将来 m − i − j m-i-j m − i − j 天,每天能获得的分数。定义 d p [ i ] [ j ] dp[i][j] d p [ i ] [ j ] 表示,当恰好达到 a = i , b = j a=i,b=j a = i , b = j 的状态时,能够获得的最高分。
初始状态为 v [ x i ] [ y i ] = z i v[x_i][y_i]=z_i v [ x i ] [ y i ] = z i ,类似二维前缀和,递推可得,v[i][j]+=v[i-1][j]+v[i][j-1]-v[i-1][j-1]
。
有状态转移方程,d p [ i ] [ j ] = v [ i ] [ j ] + max ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) dp[i][j]=v[i][j]+\max(dp[i-1][j],dp[i][j-1]) d p [ i ] [ j ] = v [ i ] [ j ] + max ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ]) 。
此题 x i , y i x_i,y_i x i , y i 的数据较大,因此需要进行离散化。定义两个数组 X , Y X,Y X , Y ,对 x i , y i x_i,y_i x i , y i 离散化。因此 v [ i ] [ j ] v[i][j] v [ i ] [ j ] 表示,保持 a = X [ i ] , b = Y [ j ] a=X[i],b=Y[j] a = X [ i ] , b = Y [ j ] 的状态,在将来 m − i − j m-i-j m − i − j 天,每天能获得的分数;d p [ i ] [ j ] dp[i][j] d p [ i ] [ j ] 表示,当恰好达到 a = X [ i ] , b = Y [ j ] a=X[i],b=Y[j] a = X [ i ] , b = Y [ j ] 的状态时,能够获得的最高分。
状态转移方程为 d p [ i ] [ j ] = v [ i ] [ j ] + max ( d p [ i − 1 ] [ j ] + ( X [ i ] − X [ i − 1 ] − 1 ) × v [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] + ( Y [ j ] − Y [ j − 1 ] − 1 ) × v [ i ] [ j − 1 ] ) 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]) d p [ i ] [ j ] = v [ i ] [ j ] + max ( d p [ i − 1 ] [ j ] + ( X [ i ] − X [ i − 1 ] − 1 ) × v [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] + ( Y [ j ] − Y [ j − 1 ] − 1 ) × v [ i ] [ j − 1 ]) ,从 X [ i − 1 ] X[i-1] X [ i − 1 ] 过渡到 X [ i ] X[i] X [ i ] ,有 X [ i ] − X [ i − 1 ] − 1 X[i]-X[i-1]-1 X [ i ] − X [ i − 1 ] − 1 天获得的分数为 v [ i − 1 ] [ j ] v[i-1][j] v [ i − 1 ] [ j ] ;从 Y [ j − 1 ] Y[j-1] Y [ j − 1 ] 过渡到 Y [ j ] Y[j] Y [ j ] 同理。
假设 m m m 天结束后的状态为 a = X [ i ] , b = Y [ j ] a=X[i],b=Y[j] a = X [ i ] , b = Y [ j ] ,则获得的最高分为,d p [ i ] [ j ] + v [ i ] [ j ] × ( m − X [ i ] − Y [ i ] ) dp[i][j]+v[i][j]\times (m-X[i]-Y[i]) d p [ i ] [ j ] + v [ i ] [ j ] × ( m − X [ i ] − Y [ i ]) 。因此可以枚举结束后的状态 i , j i,j i , j 得到答案,即 a n s = max 1 ≤ i ≤ c x , 1 ≤ j ≤ c y d p [ i ] [ j ] + v [ i ] [ j ] × ( m − X [ i ] − Y [ i ] ) ans=\max\limits_{1\le i\le cx,1\le j\le cy} dp[i][j]+v[i][j]\times (m-X[i]-Y[i]) an s = 1 ≤ i ≤ c x , 1 ≤ j ≤ cy max d p [ i ] [ j ] + v [ i ] [ j ] × ( m − X [ i ] − Y [ i ]) ,其中 c x cx c x 为不同的 x i x_i x i 的个数,c y cy cy 为不同的 y i y_i y i 的个数。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 #include <iostream> #include <algorithm> #include <cstdio> #define N 1002 #define ll long long using namespace std;int n,m;ll X[N],Y[N]; ll v[N][N]; ll dp[N][N]; 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; } 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 ]; } } 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 ]); } } 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 ; }