洛谷 1280 尼克的任务

本文主要是介绍洛谷 1280 尼克的任务，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://www.luogu.org/problem/show?pid=1280
DP，看了题解之后想了好久才明白（其实也并不很明白）。。。
f[i]表示从i到n的最大空闲时间，i从n到1枚举
如果有p[j]==i，则至少要做个任务，f[i]可以从f[i+t[j]]转移过来
如果没有，则可以偷懒，f[i]=f[i+1]+1
题目给的p是有序的，所以j直接从m开始减就可以

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[10010],p[10010],t[10010],n,k;
int main()
{scanf("%d%d",&k,&n);for(int i=1;i<=n;i++)scanf("%d%d",&p[i],&t[i]);int j=n;for(int i=k;i>=1;i--){if(p[j]!=i)f[i]=f[i+1]+1;else{while(p[j]==i){f[i]=max(f[i],f[i+t[j]]);j--;}}}printf("%d",f[1]);return 0;
}

这篇关于洛谷 1280 尼克的任务的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---