ouuan 的博客

ouuan 的博客

题解 P1280 【尼克的任务】

posted on 2018-03-11 15:52:30 | under 题解 |

第一页题解没有用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;
}