一）openjudge集合问题
 

二）455.鱼塘钓鱼（fishing）
【问题描述】
        有N个鱼塘排成一排（N<100），每个鱼塘中有一定数量的鱼，例如：N=5时，如下表：

http://s6/mw690/005U6Roxzy7nZjUAF25e5&690

即：在第1个鱼塘中钓鱼第1分钟内可钓到10条鱼，第2分钟内只能钓到8条鱼，……，第5分钟以后再也钓不到鱼了。从第1个鱼塘到第2个鱼塘需要3分钟，从第2个鱼塘到第3个鱼塘需要5分钟，……
【编程任务】
　　给出一个截止时间T(T<1000)，设计一个钓鱼方案，从第1个鱼塘出发，希望能钓到最多的鱼。
　　假设能钓到鱼的数量仅和已钓鱼的次数有关，且每次钓鱼的时间都是整数分钟。
【输入格式】
　　输入文件共5行，分别表示：
　　第1行为N；
　　第2行为第1分钟各个鱼塘能钓到的鱼的数量，每个数据之间用一空格隔开；
　　第3行为每过1分钟各个鱼塘钓鱼数的减少量，每个数据之间用一空格隔开；
　　第4行为当前鱼塘到下一个相邻鱼塘需要的时间；
　　第5行为截止时间T；
【输出格式】输出文件仅一个整数（不超过231-1），表示你的方案能钓到的最多的鱼。
【输入样例】
5
10 14 20 16 9
 2   4    6   5 3
 3   5   4    4
14
【输出样例】　76
 样例解释：
第一个塘钓1分钟：得10， 然后到第2个塘，共花4分钟
第二个塘钓2分钟，得14,10，到第3个塘；共化7分钟；
第三个塘钓3分钟   20,14，8；
10+24+42=76;

【知识准备】
        最优化原理、贪心法、动态规划、用堆结构实现贪心。
【问题分析】
算法一：
        我们可以这样想：如果知道了取到最大值的情况下，人最后在第i个鱼塘里钓鱼，那么用在路上的时间是固定的，因为我们不会先跑到第i个鱼塘里钓一分钟后再返回前面的鱼塘钓鱼，这样把时间浪费在路上显然不划算，再说在你没到某个鱼塘里去钓鱼之前，这个塘里的鱼也不会跑掉（即数量不会减少）。所以这时我们是按照从左往右的顺序钓鱼的，也可以看成路上是不需要时间的，(注：指时间由独立的参数递减控制，程序不必考虑)，即人可以自由在1~i个鱼塘之间来回走，只要尽可能选取钓到的鱼多的地方就可以了，这就是我们的贪心思想。其实，这个贪心思想并不是模拟钓鱼的过程，只是统计出在各个鱼塘钓鱼的次数。程序实现时，只要分别枚举钓鱼的终
 点鱼塘（从鱼塘1到鱼塘n），每次按照上述贪心思想确定在哪些鱼塘里钓鱼，经过n次后确定后最终得到的一定是最优方案。
红色字部分最容易引人误会：程序设置了一个到鱼塘所需时间的前缀和，作为限制到达某处鱼塘的条件；在此限制下，就可以把在此到达范围内的所有鱼塘之间，都看成是不花时间的。然后，就枚举每一个鱼塘，选出其中剩鱼最多的钓。不必考虑它的次序——>由于不可能走回头路，所以顺路下来的数量，就是真实的次序。
这里所谓的贪心，其实只是动规方法（静态记录数组下的搜索）下采用的方式，它本质上已经是动规。
贪心参考：
using namespace std;
int a[105],b[105],c[105],v[105];
int main()
{ 
   int n;
   cin>>n;
   for (int i=1;i<=n;++i) cin>>a[i];//塘初始数
   for (int i=1;i<=n;++i) cin>>b[i];//塘减数
   for (int i=1;i<=n-1;++i)
   { 
           cin>>c[i];
      c[i]=c[i]+c[i-1];
        }//时间消耗
   int maxxx=0;
   int t;cin>>t;
   for (int i=1;i<=n;++i)
   {  //枚举每个池塘
           for (int j=1;j<=i;++j)  v[j]=a[j]+b[j];
     //因为剩下的鱼　y=v[k]-b[k]，所以加上b[j]，为了假定所有的鱼都可选。
           int s=t-c[i-1];//到这个塘后剩下的总时间
      int ans=0;
      for (int j=1;j<=s;++j)//在时间限度内的枚举，这是动规的方法；
       { 
             int maxx=0,xh,y;
        for (int k=1;k<=i;++k)
        {//枚举在当前之前的几个鱼塘 
                y=v[k]-b[k];//剩下的鱼
               if (y>maxx) maxx=y, xh=k;//谁剩下的鱼多，到那里钓鱼
            }//在指定的时间限定内，扫描每个池塘的最大值；
        //形成时间限度j * 每个池塘的枚举；   
        v[xh]=v[xh]-b[xh];//减去塘中减少的鱼量，以备下一个枚举；
        ans+=maxx;
             }//end for;
     maxxx=max(maxxx,ans);
   }
   cout<<maxxx;
}


算法二：
　　其实，这道题是考虑最优性问题的，所以我们也可以用动态规划来解决，假设用Opt[t][n]来表示第t分钟时，人在第n个鱼塘里钓鱼，最多所能钓到的鱼数。则：
　　Opt[t][n] =Maxinum{Opt[t-k][n-1]+S}；
　　穷举k，S为t-k+1到t之间，除去从第n-1的鱼塘走到第n个鱼塘的时间，在第n个鱼塘中可以钓到的鱼数。
动规参考：
program fishing2;         //动态规划
const maxT = 1000;
      maxF = 1000;
      maxN = 100;
type nodeP = record
                  fish,delta,time:longint;
             end;//定义结构
var Fishing:array[0..maxF+1] of longint;
    Opt,tOpt:array[0..maxT] of longint;
    Pound:array[1..maxN] of nodeP;//Pound是结构nodeP的数组
    ans,n,t,i:longint;

procedure Doit;
var i,j,k,tmp:longint;
begin
   for i:=1 to n do//n个塘
      with pound[i] do//以下操作带pound[i]前缀，每个pound表示一个池塘
        begin
           for j:=0 to t do tOpt[j]:=-maxlongint;
           fillchar(Fishing,sizeof(Fishing),0);//当前池塘的状态记录
           for j:=1 to (fish div delta+1) do Fishing[j]:=Fishing[j-1]+fish-(j-1)*delta;//最多钓的次数，每次状态
           for j:=0 to t do//时间限制，背包
              for k:=0 to fish (div delta+1) do
                 if (j+k+time) <= t then
                    begin
                        tmp:=Opt[j]+Fishing[k];
                        if tmp > tOpt[j+k+time] then tOpt[j+k+time]:=tmp;
                        if tmp > ans then ans:=tmp;
                    end;
           Opt:=tOpt;
        end
end;

begin           //main
  assign(input,'fishing.in');  reset(input);
  assign(output,'fishing.out'); rewrite(output);
  readln(n);
  for i:=1 to n do read(pound[i].fish); readln;
  for i:=1 to n do read(pound[i].delta); readln;
  for i:=1 to n-1 do read(pound[i+1].time); readln;
  readln(t);
  ans:=-maxlongint;
  Doit;                         //动态规划过程
  writeln(ans);
  close(input); close(output)
end.

算法三：
　　在算法一的基础上，建立以fish为关键字的大根堆，包括能钓到鱼的数量和池塘的编号。然后借助枚举创造条件，实现复杂度为O（m*nlogn）的算法。
参考一：优先队列
#define fish first
#define lake second
using namespace std;
priority_queue < pair < int,int >  > heap;
int t[101],f[101],d[101];
int ans,m,Max,n,k,tl,Time;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>f[i];
    for(int i=1;i<=n;i++) cin>>d[i];
    for(int i=1;i < n;i++) cin>>t[i];
    cin>>m;
    for(k=1;k<=n;k++){
        Time=m-tl;
        ans=0;
        for(int i=1;i<=k;i++) heap.push(make_pair(f[i],i));
        while(Time>0 && heap.top().fish>0){
            pair < int,int > a=heap.top();
            heap.pop(); ans+=a.fish;
            a.fish-=d[a.lake];
            heap.push(a);
            Time--;
            }
        if(ans > Max) Max=ans;
        tl +=t[k];
        }
    cout<<Max<<endl;   
    return 0;
    }
参考二：手工建大根堆
#include
#include
using namespace std;
struct Data{
    int fish,lake;
    };
Data heap[101];
int t[101],f[101],d[101];
int Max,tl;
void maintain(int i,int k){//确定每个元素i在堆中的位置；
    Data a;
    int next;
    a=heap[i];//每一次，都是最尾的那个记录；
    next=i*2;
    while(next <= k) {
        if(next < k && heap[next].fish < heap[next+1].fish) next++;
        if(a.fish < heap[next].fish){//逆序一对；
            heap[i] =heap[next];//i,next迭代记录着更换位置；heap[i]备份在a中；
            i   =next;//更新i;
            next *=2;//更新next;
            }
        else break;
        }//最后的i是空出来的，是要排序的那个a的合适位置；
    heap[i]=a;//完成赋值；
    }//i之前的堆结构已经在此前步骤中整理好；
int main(){
    int m,n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>f[i];
    for(int i=1;i<=n;i++) cin>>d[i];
    for(int i=1;i < n;i++)  cin>>t[i];
    cin>>m;
    for(int k=1;k<=n;k++) {
        int Time=m-tl;//开始时为0
        int ans=0;
        for(int i=1;i<=k;i++) {
            heap[i].fish=f[i];
            heap[i].lake=i;
            }//重新初始化堆数组；
        for(int i=1;i<=k/2;i++) maintain(i,k);//在K的范围内建立大根堆；
        while(Time >0 && heap[1].fish >0){
            ans+=heap[1].fish;
            heap[1].fish -=d[heap[1].lake];//改变了堆条件
            maintain(1,k);//重新维护堆；
            Time--;
            }   //当前最大池中，假如时间用尽的话，最大钓鱼的尾数；
        //堆的作用，是找到最大值的时间。  
        if(ans>Max) Max=ans;
        tl+=t[k];//使用过的时间；
        }
    cout<<Max<<endl;
    return 0;
    }

三）399.飞行员
查理获得了一家运输公司的定期航线。为了赢利，他必须尽可能地降低成本。他的公司有N（N是偶数）个飞行员组成的N/2个机 组。每个机组包括两个飞行员——>机长和他的助手。机长必须比他的助手年长。每个飞行员有两个可能的工资合同——>作为机长和作为助手。同一 个飞行员当机长的工资高于当助手的工资　，然后就同一个机组而言，一个助手的工资可能高于他的机长。
编程帮助查理计算将飞行员按最佳组合编组后，所需支付给飞行员的最少工资总额；

输入格式
第１行一个偶数N，2<=N<=10000，表示查理公司所有的飞行员数量
接下来的N行，包含每个飞行员的工资，按飞行员的年龄排序，最年轻的飞行员的工资排在第一个。每行包含两个整数x和y，由一个空格隔开，1<=y
输出格式
一行一个数，表示查理所需支付给飞行员的最少工资总额。

输入样例一：
6
5000 3000
4000 1000
9000 7000
11000 5000
7000 3000
8000 6000
输出样例一：
33000

输入样例二：
6
5 1
9 8
6 2
10 9
5 3
6 1
输出样例二：
31

输入样例三：
10
76 27
96 48
30 16
72 50
88 82
91 55
74 33
80 76
55 52
37 11
输出样例三：
503

【算法分析】
先列举出样例一所有情况：
6
5000 3000
4000 1000
9000 7000
11000 5000
7000 3000
8000 6000

助手	机长	费用
1、2、3	4、5、6	3000+1000+7000+11000+7000+8000=37000
1、2、4	3、5、6	3000+1000+9000+5000+7000+8000=33000
1、2、5	3、4、6	3000+1000+9000+11000+3000+8000=35000
1、3、4	2、5、6	3000+4000+7000+5000+7000+8000=34000
1、3、5	2、4、6	3000+4000+7000+11000+3000+8000=36000

显然，第二组决策最优。分析决策选出的助手的特点：
1  5000 3000               5000-3000 = 2000
2  4000 1000               4000-1000 = 3000
4  11000 5000             11000-5000 = 6000
由于一号必为助手，六号必为机长，则决策只存在于2、3、4、5号中，根据列举结果不难发现，选出的助手都是xi-yi较大的。由于有“机长必须比他的助手年长”这条限制，所以每2i-1人中必须选i个助手，选出的i个助手必然是xi-yi最大的前i名，由此便得出了正确的贪心策略。

 小结：一时想不出贪心策略时可以通过列举并分析最优解的特点来得出正确的贪心策略。

using namespace std;
priority_queue< int > maxheap;
int main(){
  int n, rez = 0, kap, zam;
  for( cin >> n; n; --n ){//最年轻的飞行员排前头
     cin >> kap >> zam;//当机长的价格，当助手的价格
     rez += kap;//到目前为止，假设都是当机长的话，需要付出的价格
     maxheap.push( kap-zam );//假如眼前这位当副手的话，在堆中会形成“副手差最大后的排前头”；
     if( n%2==0 ) { //因为第一个的工资总是最少的，年长的排在年轻的后面
         rez -= maxheap.top(); //两者之间必有一个是机长，堆维护着最优化条件（减去谁）
         maxheap.pop();//楼上那家伙已经当了副手，减去他的工资差额
　　　}
  }
  cout << rez << endl;
  return 0;
}