有一种贪心是线段覆盖，排序后从前往后扫就可以想到如果没有任务开头相同的，则就是从第一个任务开始向后扫描那么加上任务开头相同的，则对于某几个起始时间相同的，f[i]=f[i+a[k].end]，i是一个，那么不同的i+a[i].endl不一样，我们从中找最优的，这时我们发现可以倒推，然后f[i]定义也变成了最长休息时间接下来我们按照贪心的图来模拟，发现对于非起点的f[i]应该f[i]+1的来做，从而作为一个中间值给起点的最优值做铺垫
//9 2
//1 6
//5 9
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,k,f[
10005];
struct node{
int s,t;
}a[10005];
int cmp(node x,node y){
return x.s<
y.s;
}
int main()
{
scanf("%d%d",&n,&
k);
for(
int i=
1;i<=k;i++
)
{
scanf("%d%d",&a[i].s,&
a[i].t);
}
sort(a+
1,a+k+
1,cmp);
//把k写成n了
for(
int i=n;i>=
1;i--
)
{
if(i!=
a[k].s)
{
f[i]=f[i+
1]+
1;
// cout<<i<<","<<f[i]<<endl;
}
else
{
while(i==
a[k].s)
{
f[i]=max(f[i],f[i+
a[k].t]);
k--
;
// cout<<i<<","<<f[i]<<endl;
}
}
}
printf("%d\n",f[
1]);
return 0;
}
//完全背包用二维的怎么画?
转载于:https://www.cnblogs.com/caterpillor/p/9758926.html
相关资源：各显卡算力对照表！
