传送门
本题要倒着推 即从大的时间往小的时间转移 因为 如果正着 在i的时候 i+t显然还没转移
求啥设啥 要求最大的空暇时间 那么设dp[i]为i~n分钟之内可以获得的最大空暇时间
方程显然： 如果没有任务是从当前时间开始的 则dp[now]=dp[now+1]+1; 否则 dp[now]=max{dp[now+time[num]};
ans=dp[1]
#include<bits/stdc++.h> #define N 10005 #define K 10005 using namespace std; int n,k,exist[N],dp[N]; struct data { int start,time; }node[K]; inline bool cmp(const data &a,const data &b) { return a.start>b.start; } int main() { ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); cin>>n>>k; for(int i=1;i<=k;i++) { cin>>node[i].start>>node[i].time; exist[node[i].start]++; } sort(node+1,node+k+1,cmp); int num=1; for(int i=n;i>=1;i--) { if(exist[i]==0) dp[i]=dp[i+1]+1; else { for(int j=1;j<=exist[i];j++) { dp[i]=max(dp[i],dp[i+node[num].time]); num++; } } } cout<<dp[1]; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9485837.html
