Codeforces #536 div2 E （1106E）Lunar New Year and Red Envelopes (DP)

题意：过年了，Bob要抢红包。抢红包的时间段为1 - n，有m个红包，每个红包有三个属性：st（红包出现的时间）， ed（红包消失的时间），d（如果抢了这个红包，能够抢下一个红包的时间），w（红包的收益）。注：结束时间为ed是指在ed + 1的时候才能抢其它的红包，d同理。Bob是一个贪心的人，如果当前时间段他可以抢红包，他会抢现在出现的红包中收益最大的红包。如果有多个收益最大的红包，他会抢d最大的那个。Alice可以打断Bob k次，每次打断可以使Bob在1秒内无法行动，下一秒恢复正常。现在问Bob可以获得的最小的收益是多少？

思路：这种题一看就知道常规方法解决不了啦，只能DP了。首先，每个时间点抢的是什么红包其实是固定的，我们只需要先把红包按开始时间排序，然后用堆或者mutiset维护这个时间点抢什么。其次，我们可以发现，如果Bob抢了某个红包，他只有在特定的时间之后才能抢下一个红包，这是明显的状态转移过程。我们设dp[i][j]为处于时间点i，还可以打扰j次的最小收益。那么我们可以执行两种转移：

1：我们抢这个红包，（设这个红包的w为wi，d为di）那么dp[di + 1][j ] = min(dp[di + 1][j], dp[i][j] + wi)

2：现在不抢，用掉一次打扰机会，那么dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i][j]);

代码：

#include <cstdio> #include <algorithm> #include <vector> #include <iostream> #include <cstring> #include <map> #include <set> #include <bitset> #include <queue> #include <cmath> #include <string> #define INF 0x3f3f3f3f3f3f3f3f #define pii pair<int, int> #define lowbit(x) (x & (-x)) #define ls(x) (x << 1) #define rs(x) ((x << 1) | 1) #define LL long long using namespace std; const int maxn = 100010; struct node {int st, ed, d, pos;LL w;bool operator < (const node& rhs) const {if(w == rhs.w) return d < rhs.d;return w < rhs.w;} }; node a[maxn]; vector<int> b[maxn],c[maxn]; priority_queue<node> q; LL dp[maxn][210]; node re[maxn]; bool v1[maxn]; bool cmp(node x, node y) {if(x.st == y.st) return x.ed < y.ed;return x.st < y.st; } int main() {int n, k, m;scanf("%d%d%d", &n, &k ,&m);for (int i = 1; i <= m; i++) {scanf("%d%d%d%d", &a[i].st, &a[i].ed, &a[i].d, &a[i].w);}sort(a + 1, a + 1 + m);for (int i = 1; i <= m; i++) {b[a[i].st].push_back(i);c[a[i].ed].push_back(i);a[i].pos = i;}for (int i = 1; i <= n; i++) {for (int j = 0; j < b[i].size(); j++) {int y = b[i][j];q.push(a[y]);}while(q.size() && v1[q.top().pos]) {q.pop();}if(!q.empty())re[i] = q.top();else re[i] = (node) {0, 0, i, 0, 0};for (int j = 0; j < c[i].size(); j++) {int y = c[i][j];v1[y] = 1;}}memset(dp, 0x3f, sizeof(dp));dp[1][k] = 0;for (int i = 1; i <= n; i++) {for (int j = 0; j <= k; j++) {int d = re[i].d;if(j) dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i][j]);dp[d + 1][j] = min(dp[d + 1][j], dp[i][j] + re[i].w);}}LL ans = INF;for (int i = 0; i <= k; i++) {ans = min(ans, dp[n + 1][i]);}printf("%lld\n", ans); }

　　

 

转载于:https://www.cnblogs.com/pkgunboat/p/10345935.html

总结

以上是生活随笔为你收集整理的Codeforces #536 div2 E （1106E）Lunar New Year and Red Envelopes (DP)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。