链接:https://www.nowcoder.com/acm/contest/206/E
来源:牛客网
题目描述
弱弱有两个属性a和b,这两个属性初始的时候均为0,每一天他可以通过努力,让a涨1点或b涨1点。
为了激励弱弱努力学习,我们共有n种奖励,第i种奖励有xi,yi,zi三种属性,若a≥ xi且b≥ yi,则弱弱在接下来的每一天都可以得到zi的分数。
问m天以后弱弱最多能得到多少分数。
输入描述:
第一行一个两个整数n和m(1≤ n≤ 1000,1≤ m≤ 2000000000)。
接下来n行,每行三个整数xi,yi,zi(1≤ xi,yi≤ 1000000000,1≤ zi ≤ 1000000)。
输出描述:
一行一个整数表示答案。
示例1
输入
复制
2 4
2 1 10
1 2 20
输出
复制
50
备注:
在样例中,弱弱可以这样规划:第一天a涨1,第二天b涨1,第三天b涨1,第四天a涨1。
共获得0+0+20+30=50分。

dp太难了…
首先是离散化,这步很关键,然后z值对应的是一个x,y对,而不是特定的第几个奖励
定义两个状态和转移
a d d i , j add_{i,j} addi,j表示当ab满足i,j所对应的x[i]和y[j]时之后的每天能奖励多少
d p i , j dp_{i,j} dpi,j表示ab满足i,j所对应的x[i]和y[j]时最大能获得的奖励
然后状态转移就是
a d d i , j = a d d i − 1 , j + a d d i , j − 1 − a d d i − 1 , j − 1 + m p [ x [ i ] , y [ j ] ] add_{i,j}=add_{i-1,j}+add_{i,j-1}-add_{i-1,j-1}+mp[{x[i],y[j]}] addi,j=addi1,j+addi,j1addi1,j1+mp[x[i],y[j]]
前面三个就是容斥原理,然后最后一个加的就是对应的z值
d p i , j = a d d i , j + m a x ( d p i − 1 , j + ( x i − x i − 1 − 1 ) ∗ a d d i − 1 , j , d p i , j − 1 + ( y j − y j − 1 − 1 ) ∗ a d d i , j − 1 ) dp_{i,j}=add_{i,j}+max(dp_{i-1,j}+(x_i-x_{i-1}-1)*add_{i-1,j},dp_{i,j-1}+(y_j-y_{j-1}-1)*add_{i,j-1}) dpi,j=addi,j+max(dpi1,j+(xixi11)addi1,j,dpi,j1+(yjyj11)addi,j1)
对应就等于从{i,j}开始后面每天获得的奖励(这里其实就是一天)+max(分别从{i-1 j}转移和从{i,j-1}转移过来的)

代码:

#include <cstdio>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
using namespace std;
const int N=1050;
typedef long long ll;
int n,m;
ll x[N],y[N],z[N];
ll add[N][N],dp[N][N];
ll xx[N],yy[N];
set<int> xs,ys;
map<pair<int,int>,int> mp;
int main(void){
   
    scanf("%d%d",&n,&m);
    int xn=0,yn=0;
    for(int i=1;i<=n;i++){
   
        scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
        mp[{
   x[i],y[i]}]+=z[i];
    }
    sort(x+1,x+1+n);
    sort(y+1,y+1+n);
    xn=unique(x+1,x+1+n)-(x);
    yn=unique(y+1,y+1+n)-(y);
    printf("%d %d\n",xn,yn);
    for(int i=1;i<=xn;i++){
   
        for(int j=1;j<=yn;j++){
   
            add[i][j]+=add[i-1][j]+add[i][j-1]-add[i-1][j-1]+mp[{
   x[i],y[j]}];
        }
    }
    // for(int i=1;i<=xn;i++){
   
    // for(int j=1;j<=yn;j++){
   
    // printf("%lld ",add[i][j]);
    // }
    // printf("\n");
    // }
    for(int i=1;i<=xn;i++){
   
        for(int j=1;j<=yn;j++){
   
            dp[i][j]=add[i][j]+max(dp[i-1][j]+(x[i]-x[i-1]-1)*add[i-1][j],dp[i][j-1]+(y[j]-y[j-1]-1)*add[i][j-1]);
        }
    }
    // for(int i=1;i<=xn;i++){
   
    // for(int j=1;j<=yn;j++){
   
    // printf("%lld ",dp[i][j]);
    // }
    // printf("\n");
    // }
    ll ans=0;
    for(int i=1;i<xn;i++){
   
        for(int j=1;j<yn;j++){
   
            if(x[i]+y[j]<=m){
   
                ans=max(ans,dp[i][j]+(m-x[i]-y[j])*add[i][j]);
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}