题解 P1280 【尼克的任务】

xzyxzy

2017-07-15 19:57:15

Solution

很难得很难得很难得的,一道区间动规的题能不看题解(看题解写dp是个不好的习惯,请不要学习我(/笑哭/))自己推出转移方程式来,还一遍过了 ps:以前的题解动规都写成了动归,实在是尴尬。。。请谅解(/擦汗/) 那么推的过程对于我这种小蒟蒻来说,真的很复杂很复杂,推了一下午一个半小时,又码了半个小时,草稿纸A4大小的写满了好几张,顺着退啊不行又逆着推,二维不行降一维,以结束时间排序不行改按开始时间排序,折腾了好一会终于找到一个几近O(n)的高效又不炸空间的算法 好吧,进入正题 首先,要注意的是题目的时间,**时间是一段**,所以时间轴上0到1指的是第一分钟,,所以我们分析样例的时候要从0开始画时间轴,取时间段来安排尼克的任务 这点明确后,就很容易描述各个任务的起始点和结束点还有持续时间了,我们用结构体表示各个任务 然后,最重要的是>当在一个任务起始时尼克有空的话,尼克必须选 所以我们要对各个任务的开始时间进行排序,从后往前枚举开始时间的过程中,碰到一个任务就必须选(实际上因为只有这一种情况所以我们才从后往前枚举开始时间) 于是转移方程式的原理就清晰了: >从第i个时间点到第n个时间点尼克最小的工作时长 为选 以第i个时间点为起始时间的任务的工作时间 加上从那个任务的结束时间到n 的最小总工作时间(因为以同一点为起始时间的任务可能不止一个,所以选最小) 那么清楚了,就来看代码吧(详细注释) ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int n,k; int min1(int a,int b){return a<b?a:b;}//防止一些版本中没有min()函数,所以自定义一个 int read()//有一万个任务所以要读入优化 { char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); int h=0; while(ch<='9'&&ch>='0') { h=h*10+ch-48; ch=getchar(); } return h; } struct task{ int be; int fi; }a[10010];//结构体存各个任务的信息 int my(const task&a,const task&b)//开始时间晚的排前面 { if(a.be>b.be) return 1; if(a.be<b.be) return 0; if(a.fi<b.fi) return 1;//开始时间一样则结束早排前面 return 0; } int f[10001];//f[i][j]表示从第i分钟到第n分钟尼克最少的工作时间 int main() { n=read(); k=read(); for(int i=1;i<=k;i++) { int x,y; x=read(); y=read(); a[i].be=x-1; a[i].fi=x+y-1;//记录各任务的开始结束时间(这里有点特殊,不过你模拟一下就明白了(时间点和时间段的差异)) } a[k+1].be=1000000;//防止在i=0时陷入死循环 sort(a+1,a+k+1,my);//排序函数 int tt=1;//指向任务 for(int i=n-1;i>=0;i--)//枚举开始时间 { if(a[tt].be==i) { int mini=10000000; while(a[tt].be==i)//枚举到开始时间等于i时,一直把开始时间等于i的任务枚举完,这样才能找到最小值 { mini=min1(mini,a[tt].fi-a[tt].be+f[a[tt].fi]);//遇到了一个任务,那么必须选 tt++; } f[i]=mini; } else f[i]=f[i+1];//没有任务就延续之前的值 } cout<<n-f[0];//注意输出的是闲暇时间,不是工作时间 return 0; } ``` 那么这道题就解决了,其实还是很容易的吧, 所以——>千万不要看题解写dp 这样真的没有提高,状态转移方程一定要自己想 希望这篇题解在你绞尽脑汁也想不出这道题的时候对你有帮助(/认真脸/)!