题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1029
当然要按结束时间排序，然后按顺序修或跳过。就是那种“……不会使答案不优”的证明。
想了一个dp。dp[ i ][ j ]表示前 i 个建筑、修了 j 个建筑，完成的最早时间。可惜是n^2的。
dp[ i ][ j ]=min( dp[ i-1 ][ j ] , dp[ i-1 ][ j-1 ]+len[ i ] ) （dp[ i-1 ][ j-1 ]+len[ i ]<=t[ i ]）
考虑这个转移。如果有 j1>j2 && dp[ i ][ j1 ]<dp[ i ][ j2 ]，则dp[ i ][ j2 ]就是没用的。最后看的是最大的能达到的 j 。
之所以保留那些小的 j ，是因为它们结束时间可能早，可能对后面有利，就是那个dp[ i ][ j ]=dp[ i-1 ][ j-1 ]+len[ i ]的转移。
应该再仔细思考的。只考虑最大的 j ，对它有用的小 j0 其实只有 j0=j-1 。
新来一个建筑，要么是直接从最大的 j 这里变成 j+1 ，要么是继续保持 j 。为了维护 j ，需要 j-1 的值，进而有了第二维。
但其实维护 j 只需要在“继续保持 j ”的时候不要无脑跳过当前建筑，而是替换掉一个耗时更长的建筑，就能维护了！
然后就变成了那种贪心的样子。能修当前建筑就修，不然就换掉一个。
我竟然以为当 now+a[i].len>a[i].t 而又 now-q.top()+a[i].len<=a[i].t 就能说明 a[i].len<q.top()。真是蠢了。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;const int N=150005;int n,now;struct Node{ ???int len,t;}a[N];priority_queue<int> q;bool cmp(Node u,Node v){return u.t<v.t;}int main(){ ???scanf("%d",&n); ???for(int i=1;i<=n;i++)scanf("%d%d",&a[i].len,&a[i].t); ???sort(a+1,a+n+1,cmp); ???for(int i=1;i<=n;i++) ???????if(now+a[i].len<=a[i].t) ???????????now+=a[i].len,q.push(a[i].len); ???????else if(q.size()&&a[i].len<q.top()&&now-q.top()+a[i].len<=a[i].t)//a[i].len<q.top()!!! ???????????????now=now-q.top()+a[i].len,q.pop(),q.push(a[i].len); ???printf("%d\n",q.size()); ???return 0;}bzoj 1029 [JSOI2007]建筑抢修——贪心（伪dp）
原文地址：https://www.cnblogs.com/Narh/p/9366149.html