注意到反悔贪心的题基本没怎么做过。
P2949 [USACO09OPEN] Work Scheduling G
思路
注意到这是一个二维的东西，因此可能先去想 DP。但是注意到限制（时间）与贡献是独立的，因此考虑去扫时间而去维护贡献。
更准确地说，这个实际上就是一个类似 DP 的过程，但是转移只能从上一个时间转移过来。因此考虑反悔贪心的过程。
我们将每个物品挂在截止时间，这样当我们扫到一个物品，我们就直接判断其是否可以塞进当前的选的集合里面。如果当前没有更优的可以塞，那么以后也一定不可以，否则就一定可以。考虑用小根堆维护上述过程即可。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,ans=0,dm=0,l=1,r=1;
struct node
{ll d;//时间 ll p;//利润
} a[100005];
bool cmp(node x,node y)
{if(x.d!=y.d) return x.d<y.d;else return x.p>y.p;
}
priority_queue<int,vector<int>,greater<int> > q;
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i].d>>a[i].p;//dm=max(dm,a[i].d);}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){if(a[i].d<=q.size()){if(a[i].p>q.top()){ans-=q.top();q.pop();q.push(a[i].p);ans+=a[i].p;}}else{q.push(a[i].p);ans+=a[i].p;}}cout<<ans<<endl;return 0;
}