专栏首页ACM算法日常牛客国庆集训派对Day6 E-Growth(离散化DP)

牛客国庆集训派对Day6 E-Growth(离散化DP)

链接:https://ac.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

1.离散化:是为了把重复的x,y去除,以便进行sort和dp。

unique()是c++ STL库里的函数,其功能是去除相邻的重复元素(只保留一个),所以使用前需要排序

2. 设两个转移方程:

v[i][j]表示当到第i X时和第j Y时,v[i][j]接下来每天能增长的量。

转移 : v[i][j]=v[i−1][j]+v[i][j−1]−v[i−1][j−1]+t[i][j]

这一步其实可以用lower-bound进行二分查找,就省得自己写二分了

设dp[i][j]为到第i X和第j Y时的最大值

转移:

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])

(X[i]−X[i−1]−1),(Y[j]−Y[j−1]−1)都表示天数。

#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
#define maxx 1005
using namespace std;
struct  node
{
    int x,y,z;
}p[maxx];//变量存储
long long  X[maxx];//分别离散化处理x,y
long long  Y[maxx];
long long v[maxx][maxx];//v[i][j]接下来每天能增长的量
long long dp[maxx][maxx];//dp[i][j]为到第i和j时的最大值
int cnt1,cnt2,cnt;//分别用以计算X[MAXX],Y[MAXX]和P[MAXX]的个数
int main()
{
    int n,m;
    cin>>n>>m;
    int x,y,z;
    for(int i=1;i<=n;i++){//变量的初始化
        scanf("%d%d%d",&x,&y,&z);
        if(x+y>m)continue;
        p[++cnt].x=x;
        p[cnt].y=y;
        p[cnt].z=z;
        X[++cnt1]=x;
        Y[++cnt2]=y;
    }
    sort(X+1,X+1+cnt1);//离散化去重处理
    cnt1=unique(X+1,X+1+cnt1)-X-1;
    sort(Y+1,Y+1+cnt2);
    cnt2=unique(Y+1,Y+1+cnt2)-Y-1;
    for(int i = 1; i <= n; i++) {
        int cn = lower_bound(X+1,X+1+cnt1,p[i].x) -X;
        int cy = lower_bound(Y+1,Y+1+cnt2,p[i].y) -Y;
        v[cn][cy] +=p[i].z;
    }
    for(int i=1;i<=cnt1;i++)
    for(int j=1;j<=cnt2;j++)
        v[i][j]+=v[i-1][j]+v[i][j-1]-v[i-1][j-1];
    for(int i=1;i<=cnt1;i++)
    for(int j=1;j<=cnt2;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]);
    long long ans=0;
    for(int i=1;i<=cnt1;i++)
    for(int j=1;j<=cnt2;j++)
        if(X[i]+Y[j]<=m)ans=max(ans,dp[i][j]+(m-X[i]-Y[j])*v[i][j]);
        //(m-X[i]-Y[j])为剩余天数能拿到的固定收益
    cout<<ans<<endl;
    return 0;
}

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:mxg

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 周赛题解 211

    遍历字符串,记录每个字符第一次出现的位置。当某个字符再次出现时,说明找到了相同的两个字符,那就更新一下最大长度。

    ACM算法日常
  • Codeforces Round #668 (Div. 2)A-D

    给出一个长度为 n 的排列,排列 p 的定义是,对于任意一个 p[ i ] 来说,其取值范围为 [ 1 , n ] ,且任意两个元素互不相等题目规定函数

    ACM算法日常
  • 水果Fruit(母函数) - HDU 2152

    转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 ...

    ACM算法日常
  • HPU 18级个人积分赛--first

    J. Worker 思路:我们仔细分析一下题意,给了n个厂,m个人,假设每个厂的福利原因使得工人的工作能力不同,然后你要把这m个人分给n个厂,使得每个厂的总效...

    用户7727433
  • nyoj-----42一笔画问题

    一笔画问题 时间限制:3000 ms  |  内存限制:65535 KB 难度:4 描述 zyc从小就比较喜欢玩一些小游戏,其中就包括画一笔画,他想请你帮他写一...

    Gxjun
  • 有关dp问题的机器人走地图

    今天俺和大佬交流的时候,发现了一个经典问题。就是机器人走方格问题~ 一开始没在意想到了杭电曾做过的一道题类似题当初俺是用打表的好像,回来之后细想这个跟那个好像...

    用户7727433
  • 19 nowcoder 第二场 经典dp延伸,单调队列变量维护 H Second Large Rectangle

    题意: n*m大小的矩形 n,m<1000。 s[ i ][ j ] 只包含 0 和 1,求 只包含1 的第二大矩形面积。

    用户2965768
  • 剑指offer——机器人的运动范围

    题目描述 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和...

    AI那点小事
  • 和为0的最长连续子数组【转载+优化代码】

    题目描述和思路来自博客:http://www.cnblogs.com/coding-wtf/p/5849222.html,在此表示感谢。

    xiaoxi666
  • HDU 2389 Rain on your Parade(二分图最大匹配--Hopcroft-Karp算法)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2389

    Ch_Zaqdt

扫码关注云+社区

领取腾讯云代金券