題意：過年了，Bob要搶紅包。搶紅包的時(shí)間段為1 - n，有m個(gè)紅包，每個(gè)紅包有三個(gè)屬性：st（紅包出現(xiàn)的時(shí)間）， ed（紅包消失的時(shí)間），d（如果搶了這個(gè)紅包，能夠搶下一個(gè)紅包的時(shí)間），w（紅包的收益）。注：結(jié)束時(shí)間為ed是指在ed + 1的時(shí)候才能搶其它的紅包，d同理。Bob是一個(gè)貪心的人，如果當(dāng)前時(shí)間段他可以搶紅包，他會(huì)搶現(xiàn)在出現(xiàn)的紅包中收益最大的紅包。如果有多個(gè)收益最大的紅包，他會(huì)搶d最大的那個(gè)。Alice可以打斷Bob k次，每次打斷可以使Bob在1秒內(nèi)無法行動(dòng)，下一秒恢復(fù)正常。現(xiàn)在問Bob可以獲得的最小的收益是多少？

思路：這種題一看就知道常規(guī)方法解決不了啦，只能DP了。首先，每個(gè)時(shí)間點(diǎn)搶的是什么紅包其實(shí)是固定的，我們只需要先把紅包按開始時(shí)間排序，然后用堆或者mutiset維護(hù)這個(gè)時(shí)間點(diǎn)搶什么。其次，我們可以發(fā)現(xiàn)，如果Bob搶了某個(gè)紅包，他只有在特定的時(shí)間之后才能搶下一個(gè)紅包，這是明顯的狀態(tài)轉(zhuǎn)移過程。我們?cè)O(shè)dp[i][j]為處于時(shí)間點(diǎn)i，還可以打擾j次的最小收益。那么我們可以執(zhí)行兩種轉(zhuǎn)移：

1：我們搶這個(gè)紅包，（設(shè)這個(gè)紅包的w為wi，d為di）那么dp[di + 1][j ] = min(dp[di + 1][j], dp[i][j] + wi)

2：現(xiàn)在不搶，用掉一次打擾機(jī)會(huì)，那么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); }

　　

?

轉(zhuǎn)載于:https://www.cnblogs.com/pkgunboat/p/10345935.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces #536 div2 E （1106E）Lunar New Year and Red Envelopes (DP)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。