Nikonikoni~~

題目傳送門

這是當時學長講dp的第一道例題，我還上去獻了個丑，然鵝學長講的方法我似董非董(???

我當時說的怎么設計這道題的狀態，但是好像說的是二維，本題數據范圍均在10000級別，n2肯定會空間炸掉的（然而我當時還不懂...）

所以本題的狀態肯定是一維的。

今天再做這道題，狀態很容易出來了，設f[i]為1~i時間（到第i刻）的最大閑暇時間。然后日常不會推轉移方程Orz。題解真香。

但，這個狀態看似是正確的而且很可做的樣子，但是我們仔細一想就會發現在這個狀態下轉移的漏洞：

　　如果當前時刻有很多可以開始的任務，但他們的結束時間可能各不相同，那么所能獲得的閑暇時間就各有優劣了。正推看來是有弊病的。

那么我們就選擇逆推：

設f[i]表示i~n所能獲得的最大閑暇時間。我們還需要統計當前時刻有沒有任務開始了。

　　如果當前時刻沒有任務，就繼承i+1時刻的閑暇狀態；f[i]=f[i+1]+1；

　　如果當前時刻有任務，就掃一遍當前時刻開始的全部任務，看從他們中誰的結束時間轉移而來所收獲的閑暇最多；即? ? ?f[i]=max{f[i+task[++pos].endd]}。pos是我們記錄當前到第幾個任務的量，由于逆推，我們初始需要把任務按開始時間從大到小進行排序。

Code

1 #include<cstdio> 2 #include<algorithm> 3 4 using namespace std; 5 6 int n,m,pos; 7 int f[20000],sum[20000]; 8 struct node{ 9 int beginn,endd; 10 }task[20000]; 11 12 bool cmp(node a,node b) 13 { 14 return a.beginn>b.beginn; 15 } 16 17 int main() 18 { 19 scanf("%d%d",&n,&m); 20 for(int i=1;i<=m;i++) 21 scanf("%d%d",&task[i].beginn,&task[i].endd),sum[task[i].beginn]++; 22 sort(task+1,task+1+m,cmp); 23 for(int i=n;i>=1;i--) 24 { 25 if(!sum[i]) f[i]=f[i+1]+1; 26 else 27 for(int j=1;j<=sum[i];j++) 28 f[i]=max(f[i],f[i+task[++pos].endd]); 29 } 30 printf("%d",f[1]); 31 return 0; 32 } View Code

?

轉載于:https://www.cnblogs.com/nopartyfoucaodong/p/9530802.html

總結

以上是生活随笔為你收集整理的Luogu P1280 Niko的任务【线性dp】By cellur925的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。