Output
For each set of products, the program prints on the standard output the profit of an optimal selling schedule for the set. Each result is printed from the beginning of a separate line.
Sample Input
4 50 2 10 1 20 2 30 1
7 20 1 2 1 10 3 100 2 8 2
5 20 50 10
Sample Output
80
185
Hint
The sample input contains two product sets. The first set encodes the products from table 1. The second set is for 7 products. The profit of an optimal schedule for these products is 185.
#include
#include
#include
#include
#include
#include
using namespace std;
struct node
{
int p, d;
} fei[10001];
int a[10001];
bool operator < (const node& a, const node& b)
{
return a.p > b.p;
}
int main()
{
int n, i, j, s, x;
while(scanf("%d",&n)!=EOF)
{
s = 0;
memset(a,0,sizeof(a));
for(i=0; i scanf("%d%d",&fei[i].p,&fei[i].d); sort(fei,fei+n); for(i=0; i { x=fei[i].d; if(a[x]==0) { s = s + fei[i].p; a[x]++; } else { for(j=x-1; j>=1; j--) { if(a[j]==0) { s=s+fei[i].p; a[j]++; break; } } } } printf("%d\n",s); } return 0; }