题目链接:http://poj.org/problem?id=1456
题意:
有N件商品,分别给出商品的价值和销售的最后期限,每天仅可售出一件商品,求最大利润。
题解:
贪心
用visit数组标记当天是否有商品售出,将商品的价值从大到小排序,依次取出商品,从它的最后期限向前扫描出没有商品售出的一天。这样就可以得到最大销售量。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 10010 
using namespace std;
struct node
{
    int pf,dl;
}f[N];
bool vis[N];
int n;
bool operator <(node a,node b)
{
    return a.pf>b.pf;
}
int main()
{
    int maxprofit=0;
    while(~scanf("%d",&n))
    {
        maxprofit=0;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)   scanf("%d%d",&f[i].pf,&f[i].dl);
        sort(f+1,f+n+1);
        for(int i=1;i<=n;i++)
        {
            int j=f[i].dl;
            while(vis[j]!=0&&j) j--;
            if(j>0) 
            {
                maxprofit+=f[i].pf;
                vis[j]=1;
            } 
        }
        printf("%d\n",maxprofit);
    }
    return 0;
}