这道题虽然很基础但是也不是很好想……
我们一开始会想，用dp[i]表示前i分钟最大休息时间，之后你就完全不知道怎么转移了。
阻碍你转移的关键问题在于，你不知道后面会发生什么，但是如果从后面倒着DP的话就可以了。因为这样的话，你后面的过程相当于是已知的。我们只要在记录一下以这个点为开始的工作有多少，之后直接从那个工作的结束转移过来即可。如果没工作，直接从上一个位置转移即可。
看一下代码。
#include#include #include #include #include #include #include #define rep(i,a,n) for(int i = a;i <= n;i++)#define per(i,n,a) for(int i = n;i >= a;i--)#define enter putchar('\n')using namespace std;typedef long long ll;const int M = 20005;const int INF = 1000000009;int read(){ int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op;}struct mis{ int p,t; bool operator < (const mis &g) const { return p > g.p; }}a[M];int n,k,sum[M],dp[M],cnt = 1;int main(){ n = read(),k = read(); rep(i,1,k) a[i].p = read(),a[i].t = read(),sum[a[i].p]++; sort(a+1,a+1+k); per(i,n,1) { if(!sum[i]) dp[i] = dp[i+1] + 1; else { rep(j,1,sum[i]) dp[i] = max(dp[i + a[cnt].t],dp[i]),cnt++; } } printf("%d\n",dp[1]); return 0;}