题目链接：
POJ 1456 Supermarket
题意：
给出一些物品的价值和最晚出售日期，一个物品可以在最晚出售日期之前或者当天出**售，每天最多只能出售一件物品，问售出这些物品可获得的最大价值是多少。
分析：
先把这些物品按照价值从大到小排序，对于第i个物品其最晚出售日期为d，优先在d天出售，如果d天已经有物品出售了那就从d-1开始向前寻找还没被占用的日期，如果找到了就在这一天出售的i，这天也就被占用了，否则就无法出售i。
因为是按照价值从大到小选择出售的，所以如果对于无法出售的i，在其最晚出售日期d之前（包括这一天）出售的每一件物品的价值都大于等于i的价值，这样就保证了得到的最终值就是最优解。
CODE：
//796K 125MS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;const int maxn=10010;int n,ans,vis[maxn],val,d;struct Good{int val,deadline;
}good[maxn];bool cmp(struct Good a,struct Good b)
{return a.val>b.val;
}int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);
#endifwhile(~scanf("%d",&n)){for(int i=0;i<n;i++){scanf("%d%d",&val,&d);good[i].val=val;good[i].deadline=d;}sort(good,good+n,cmp);memset(vis,0,sizeof(vis));ans=0;for(int i=0;i<n;i++){d=good[i].deadline;val=good[i].val;if(!vis[d]){ans+=val;vis[d]=1;//printf("i=%d val=%d deadline=%d\n",i,val,d);}else{for(int j=d-1;j>=1;j--){if(!vis[j]){vis[j]=1;ans+=val;//printf("i=%d val=%d deadline=%d\n",i,val,d);break;}}}}printf("%d\n",ans);}return 0;
}