這道題我一直按照往常的思路想
f[i]為前i個(gè)任務(wù)的最大空暇時(shí)間
然后想不出來怎么做……
后來看了題解
發(fā)現(xiàn)這里設(shè)的狀態(tài)是時(shí)間，不是任務(wù)
自己思維還是太局限了，題做得太少。

很多網(wǎng)上題解都反著做，那么麻煩干嘛

設(shè)f[i]為前i時(shí)間內(nèi)的最大空暇時(shí)間。
這里是更新后來的狀態(tài)，和以前不一樣。
如果i為某個(gè)任務(wù)的開始時(shí)間，則
f[i+t-1] = max(f[i+t-1], f[i])
也就是繼承過去，取max
如果不是的話
f[i] = max(f[i], f[i-1] + 1)
加上獲得的空暇時(shí)間
最后輸出f[time],time為總時(shí)間

#include<cstdio> #include<cstring> #include<algorithm> #define REP(i, a, b) for(int i = (a); i < (b); i++) using namespace std;const int MAXN = 11234; int f[MAXN], time, n; struct node {int l, r;bool operator < (const node& rhs) const{return l < rhs.l || (l == rhs.l && r < rhs.r); } }a[MAXN];int main() {scanf("%d%d", &time, &n);REP(i, 1, n + 1) scanf("%d%d", &a[i].l, &a[i].r);sort(a + 1, a + n + 1);memset(f, -63, sizeof(f));f[0] = 0;int p = 1;REP(i, 1, time + 1){if(a[p].l == i){while(a[p].l == i)f[i + a[p].r - 1] = max(f[i + a[p].r - 1], f[i-1]), p++;}else f[i] = max(f[i], f[i-1] + 1);}printf("%d\n", f[time]);return 0; }

---

后來做到洛谷P1280，竟然做不出來了，看來對題解還是沒有深刻的理解
（1）初始化問題。本來以為全部都是0無所謂的，然后就WA。
因?yàn)榍笞畲?#xff0c;所以初始化為最小，同時(shí)f[0] = 0
（2）這里推時(shí)間是從f[i-1]推，不是f[i]

?

?

然后我發(fā)現(xiàn)把這個(gè)f數(shù)組輸出來亂七八糟的。
但是答案是對的
有點(diǎn)迷（因?yàn)橄聵?biāo)是時(shí)間？？）

最后，這11天過來我的代碼風(fēng)格還是有少許改變的

#include<cstdio> #include<algorithm> #include<cstring> #define REP(i, a, b) for(int i = (a); i < (b); i++) #define _for(i, a, b) for(int i = (a); i <= (b); i++) using namespace std;const int MAXN = 112345; int f[MAXN], n, k; struct node { int l, r;void read() { scanf("%d%d", &l, &r); r = l + r - 1; }bool operator < (const node& rhs) const{return l < rhs.l || (l == rhs.l && r < rhs.r);} }a[MAXN];int main() {scanf("%d%d", &n, &k);REP(i, 0, k) a[i].read();sort(a, a + k);memset(f, -63, sizeof(f));f[0] = 0;int p = 0;_for(i, 1, n){if(a[p].l == i){while(a[p].l == i) f[a[p].r] = max(f[a[p].r], f[i-1]), p++;}else f[i] = max(f[i], f[i-1] + 1);}printf("%d\n", f[n]);return 0; }

?

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

總結(jié)

以上是生活随笔為你收集整理的洛谷P1280 caioj 1085 动态规划入门（非常规DP9：尼克的任务）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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