4022：【GESP2309五级】巧夺大奖

小明参加了一个巧夺大奖的游戏节目。主持人宣布了游戏规则：

1、游戏分为n 个时间段，参加者每个时间段可以选择一个小游戏。

2、游戏中共有n 个小游戏可供选择。

3、每个小游戏有规定的时限和奖励。对于第i 个小游戏，参加者必须在第Ti 个时间段结束前完成才能得到奖励Ri 。

小明发现，这些小游戏都很简单，不管选择哪个小游戏，他都能在一个时间段内完成。关键问题在于，如何安排每

个时间段分别选择哪个小游戏，才能使得总奖励最高？

输入第一行，包含一个正整数n 。 n既是游戏时间段的个数，也是小游戏的个数。约定1≤n≤500 。

输入第二行，包含n 个正整数。第i 个正整数为 Ti，即第i 个小游戏的完成期限。约定1≤Ti≤n 。

输入第三行，包含n 个正整数。第i 个正整数为 Ri，即第i 个小游戏的完成奖励。约定1≤Ri≤1000 。

输出一行，包含一个正整数C ，为最高可获得的奖励。

样例解释1

7个时间段可分别安排完成第4、2、3、1、6、7、5个小游戏，其中第4、2、3、1、7个小游戏在期限内完成。因此，可以获得总计40+60+50+70+10=230 的奖励

解析：

测试数据

7

4 2 4 3 1 4 6

70 60 50 40 30 20 10

按完成时间排序

1 2 3 4 4 4 6

30 60 40 70 50 20 10

倒着选择游戏

6 可选为10

剩余：

1 2 3 4 4 4 6

30 60 40 70 50 20 -

5 因为可以拖延到5完成的游戏 只有6对应的10，10已被选择，所以5无可选游戏

剩余：

1 2 3 4 4 4 6

30 60 40 70 50 20 -

4 可选为70 50 20，选最大值70

剩余：

1 2 3 4 4 4 6

30 60 40 - 50 20 -

3 可选为4-50 4-20 3-40，选最大值50

剩余：

1 2 3 4 4 4 6

30 60 40 - - 20 -

2 可选为4-20 3-40 2-60，选最大值60

剩余：

1 2 3 4 4 4 6

30 - 40 - - 20 -

1 可选为4-20 3-40 1-30，选最大值40

剩余：

1 2 3 4 4 4 6

30 - - - - 20 -

最终数据：

6 5 4 3 2 1

10 0 70 50 60 40

40+60+50+70+10=230

#include <bits/stdc++.h> using namespace std; /* run this program using the console pauser or add your own getch, system("pause") or input loop */ int n; struct x{ int t,r; }; x a[500]; bool cmp(x a,x b){ if(a.t==b.t){ return a.r>b.r; } else return a.t>b.t; } int main(int argc, char** argv) { scanf("%d",&n); for(int i=0;i<n;i++)scanf("%d",&a[i].t); for(int i=0;i<n;i++)scanf("%d",&a[i].r); sort(a,a+n,cmp); /*for(int i=0;i<n;i++){ printf("%d-%d ",a[i].t,a[i].r); } cout<<endl;*/ long long sum=0; x *p_max; for(int i=a[0].t;i>0;i--){ p_max=NULL; for(int j=0;j<n;j++){ if(a[j].t>=i){ if(a[j].r>0){ if(p_max==NULL)p_max=&a[j]; else if(a[j].r>p_max->r)p_max=&a[j]; } } else break; } if(p_max!=NULL){ sum+=p_max->r; //cout<<p_max->r<<" "; p_max->r=0; } } cout<<sum; /*测试数据 7 4 2 4 3 1 4 6 70 60 50 40 30 20 10 按完成时间排序 1 2 3 4 4 4 6 30 60 40 70 50 20 10 倒着选择游戏 6 可选为10 剩余： 1 2 3 4 4 4 6 30 60 40 70 50 20 - 5 因为可以拖延到5完成的游戏 只有6对应的10，10已被选择，所以5无可选游戏 剩余： 1 2 3 4 4 4 6 30 60 40 70 50 20 - 4 可选为70 50 20，选最大值70 剩余： 1 2 3 4 4 4 6 30 60 40 - 50 20 - 3 可选为4-50 4-20 3-40，选最大值50 剩余： 1 2 3 4 4 4 6 30 60 40 - - 20 - 2 可选为4-20 3-40 2-60，选最大值60 剩余： 1 2 3 4 4 4 6 30 - 40 - - 20 - 1 可选为4-20 3-40 1-30，选最大值40 剩余： 1 2 3 4 4 4 6 30 - - - - 20 - 最终数据： 6 5 4 3 2 1 10 0 70 50 60 40 40+60+50+70+10=230 */ return 0; }