题意概括
线性资源分配的问题,因为空闲的时间大小看后面的时间(反正感觉这个就是个套路)所以从后往前DP。
转移方程
如果当前时刻没有工作
f[i]=f[i+1]+1
如果当前时刻有工作
f[i]=max(f[i],f[i+时间段])
完整代码
#include <bits/stdc++.h>
using namespace std;
map<int,int> f,sum;
int p;
struct node
{
int ks,js;
}num[10005];
bool cmp(node a,node b)
{
return a.ks>b.ks;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,k;
cin>>n>>k;
for(int i=0;i<k;i++)
cin>>num[i].ks>>num[i].js,sum[num[i].ks]++;
sort(num,num+k,cmp);
for(int i=n;i;i--)
{
if(!sum[i])
f[i]=f[i+1]+1;
else for(int j=0;j<sum[i];j++)
f[i]=max(f[i],f[i+num[p++].js]);
}
cout<<f[1];
}