【codeforces E. Lunar New Year and Red Envelopes】【贪心】【优先队列维护】【dp】【好题】

本文主要是介绍【codeforces E. Lunar New Year and Red Envelopes】【贪心】【优先队列维护】【dp】【好题】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:

有n个红包,每个红包可以在[si,ti]的时间内拾起,拾起后获得wi元,但是到di这个时刻都不能再获取其他红包

a非常贪心,他在每一时刻,如果这个时刻可以拾起红包,它会拾起金额最大的,如果同时有多个金额最大的

他会拾起di最大的

有m次干扰他的机会,每次干扰他使得他在某个时刻不能拾起红包他的女儿可以

如果他的女红采用最优操作,他最少获得多少金钱

 

思路:

我们发现在某个时刻如果可以拾起红包,那么这个红包已经确定,可以用优先队列预处理

再考虑dp[i][j]表示在第i个时刻,用了j次机会的最少金币dp[i][j]表示在第i个时刻,用了j次机会的最少金币

有两个转移有两个转移

一个是这个时刻如果没有红包可以拿那么一个是这个时刻如果没有红包可以拿那么

dp[i+1][j]=min(dp[i+1][j],dp[i][j])dp[i+1][j]=min(dp[i+1][j],dp[i][j])

如果有红包可以拿

dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j])dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j])

dp[di+1][j]=min(dp[di+1][j],dp[i][j]+wi)

【代码】

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxn = 1e5 + 6;
const ll inf = 0x3f3f3f3f3f3f3f3f;struct node {ll s, t, d, w;bool operator <(const node &r)const {if (w == r.w)return d < r.d;return w < r.w;}
}k[maxn];ll gt[maxn];
ll nxt[maxn];
ll dp[maxn][202];ll cmp(node &a, node &b) {return a.s < b.s;
}
int main() {ll n, m, p;while (~scanf("%lld%lld%lld", &n, &m, &p)) {for (ll i = 1; i <= p; i++) {scanf("%lld%lld%lld%lld", &k[i].s, &k[i].t, &k[i].d, &k[i].w);}sort(k + 1, k + 1 + p, cmp);priority_queue<node>q;ll cnt = 1;for (ll i = 1; i <= n; i++) {while (cnt <= p && k[cnt].s <= i) {q.push({ k[cnt++] });}while (q.size() && q.top().t < i)q.pop();if (q.size()) {node tmp = q.top();gt[i] = tmp.w;nxt[i] = tmp.d + 1;}else {gt[i] = 0;nxt[i] = i + 1;}}memset(dp, inf, sizeof(dp));for (ll i = 0; i <= m; i++)dp[1][i] = 0;for (ll i = 1; i <= n; i++) {for (ll j = 0; j <= m; j++) {if (gt[i]) {dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]);dp[nxt[i]][j] = min(dp[nxt[i]][j], dp[i][j] + gt[i]);}else {dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);}}}ll res = inf;for (ll i = 0; i <= m; i++) {res = min(res, dp[n + 1][i]);}printf("%lld\n", res);}
}

 

这篇关于【codeforces E. Lunar New Year and Red Envelopes】【贪心】【优先队列维护】【dp】【好题】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/244714

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

uva 10154 DP 叠乌龟

题意: 给你几只乌龟,每只乌龟有自身的重量和力量。 每只乌龟的力量可以承受自身体重和在其上的几只乌龟的体重和内。 问最多能叠放几只乌龟。 解析: 先将乌龟按力量从小到大排列。 然后dp的时候从前往后叠,状态转移方程: dp[i][j] = dp[i - 1][j];if (dp[i - 1][j - 1] != inf && dp[i - 1][j - 1] <= t[i]

uva 10118 dP

题意: 给4列篮子,每次从某一列开始无放回拿蜡烛放入篮子里,并且篮子最多只能放5支蜡烛,数字代表蜡烛的颜色。 当拿出当前颜色的蜡烛在篮子里存在时,猪脚可以把蜡烛带回家。 问最多拿多少只蜡烛。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cs

uva 10069 DP + 大数加法

代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>#include <cl