题解 P1280 【尼克的任务】
ouuan
2018-03-11 15:52:30
第一页题解没有用vector存每个开始时间的所有任务持续时间的，所以发上来。
虽然只是优化一下任务存储和查询，但还是先说方程：
f(i)表示第i~n分钟（第i分钟没有在做任务）能获得的最大空暇
f(i)=有工作?max(f(i+工作时长)):f(i+1)+1
用vector<int> w[p]存储从p开始的所有工作的持续时间，就可以方便的查询了
```
#include <iostream>
#include <vector>
using namespace std;
int f[10010],n,k;
vector<int> w[10010];
int main()
{
int i,j,p,t;
cin>>n>>k;
for (i=0;i<k;++i)
{
cin>>p>>t;
w[p].push_back(t);
}
for (i=n;i>0;--i)
{
if (w[i].size()==0)
{
f[i]=f[i+1]+1;
}
else
{
for (j=0;j<w[i].size();++j)
{
f[i]=max(f[i],f[i+w[i][j]]);
}
}
}
cout<<f[1];
return 0;
}
```