Luogu P1280 Niko的任务【线性dp】By cellur925

Nikonikoni~~

题目传送门

这是当时学长讲dp的第一道例题，我还上去献了个丑，然鹅学长讲的方法我似董非董(???

我当时说的怎么设计这道题的状态，但是好像说的是二维，本题数据范围均在10000级别，n²肯定会空间炸掉的（然而我当时还不懂...）

所以本题的状态肯定是一维的。

今天再做这道题，状态很容易出来了，设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

Luogu P1280 Niko的任务【线性dp】By cellur925

相关推荐