题解 P1280 【尼克的任务】
xzyxzy
2017-07-15 19:57:15
很难得很难得很难得的,一道区间动规的题能不看题解(看题解写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
这样真的没有提高,状态转移方程一定要自己想
希望这篇题解在你绞尽脑汁也想不出这道题的时候对你有帮助(/认真脸/)!