求助！！这体怎么写！！！ [复制链接]

  3.    学习计划（plan）

哈里波特终于离开了可怕的舅舅家，来到了Hogwarts的魔法学校学习魔法。魔法的世界是多么的神奇，小哈利对一切都充满了好奇。他想尽可能多的学习魔法。现在的问题是有些魔法课的时间有冲突，哈利无法在一天内上所有的魔法课。所以需要你写一个程序来帮助哈里波特制定一个学习计划，来安排第一天的学习，使得他能尽可能地上更多的魔法课。注意，上课的时间是不能改变的。而且上课的时候不能迟到也不能早退，否则魔法老师会对哈利产生不满。可以假设从一个教室到另一个教室的时间短得忽略不计。另外，在Hogwarts的魔法世界里，是不使用24小时制的计时方法的，它只是简单的使用一个整数来表示当时的时间。

输入：每个测试数据开头是一个整数n（1<=n<=1000），表示魔法课的总数。接下来n行，每行包括两个正整数s、t，分别表示该魔法课的上课时间和下课时间。其中s<t。

输出：对于每个测试数据，在单独一行内输出哈利所能上的最多魔法课数。

样例：

输入（plan.in）：

      3

1  15

2  19

15  17

输出（plan.out）：

  2

动态规划

引用第1楼weijifeng于2008-04-22 18:21发表的 dongRe:求助！！这体怎么写！！！ :
动态规划

这句话我已听过N遍了
动归方程怎么写

把出现的所有时间排序，然后依次求出到第二、三.......n个时间点的最多课程。计算第i个节点的方法是找出以i时间点结束的课程的起始时间点，然后用起始时间点的课程数加上1，并与i-1比较求出最大值

引用第3楼cuihaitao于2008-04-23 08:45发表的 个人意见 :
把出现的所有时间排序，然后依次求出到第二、三.......n个时间点的最多课程。计算第i个节点的方法是找出以i时间点结束的课程的起始时间点，然后用起始时间点的课程数加上1，并与i-1比较求出最大值

为什么要排序

//Harry Potter
#include <iostream>
#include <string>
#include <fstream>
#define max 1000
int mem[max-1][1];//纪录开课时间和结束时间
int f[max-1];    //记忆数组 ---f表示如果一定要选第i门课
                          //且1~i-1节课都不选，则最多可以上多少门课。
                      //谢谢perry。。

using namespace std;

int main()
...{
ifstream in("in.txt");
ofstream out("out.txt");

int tmp;
int i_count;
in >>i_count;
for (int i=0;i<i_count;++i)
...{
in >>mem[0] >>mem[1];   
}//end for

for(int i=0;i<i_count-1;i++)
for(int j=i+1;j<i_count;j++)
if(mem[0]>mem[j][0])
...{
tmp=mem[0];mem[0]=mem[j][0];mem[j][0]=tmp;
tmp=mem[1];mem[1]=mem[j][1];mem[j][1]=tmp;
}


f[i_count-1]=1;//最后一课

for (int i=i_count-2;i>=0;i--)
...{
tmp=0;
for (int j=i+1;j<i_count;j++)
...{
if( (mem[1]<mem[j][0]) && (f[j]>tmp) )
tmp=f[j];
f=tmp+1;//
}//end for j

}//end for i
tmp=0;
for (int i=0;i<i_count;i++)
...{
if (f>tmp) tmp=f;   
}
out <<tmp;
cout <<tmp<<endl;
system("pause");   
return 0;
}//end main

贪心法，样例测试通过
program plan(input,output);
const maxn=1000;
var ans,i,j,n:longint;
    left,right:array[1..maxn] of longint;
    opt:array[1..maxn] of boolean;
procedure setio;
  begin
    assign(input,'plan.in');
    assign(output,'plan.out');
    reset(input);
    rewrite(output);
  end;
procedure swap(var a,b:longint);
  var tmp:longint;
  begin
    tmp:=a;
    a:=b;
    b:=tmp;
  end;
procedure init;
  begin
    readln(n);
    for i:=1 to n do
      begin
        readln(left,right);
        if left>right then
          swap(left,right);
      end;
    fillchar(opt,sizeof(opt),true);
    close(input);
  end;
procedure solve;
  procedure qsort;
    procedure sort(l,r: longint);
      var i,j,x,y: longint;
      begin
        i:=l;
        j:=r;
        x:=right[(l+r) div 2];
        repeat
          while right<x do
            inc(i);
          while x<right[j] do
          dec(j);
          if not(i>j) then
            begin
              y:=right;
              right:=right[j];
              right[j]:=y;
              y:=left;
              left:=left[j];
              left[j]:=y;
              inc(i);
              dec(j);
            end;
        until i>j;
        if l<j then
          sort(l,j);
        if i<r then
          sort(i,r);
      end;
    begin
      sort(1,n);
    end;
  begin
    qsort;
    for i:=1 to n do
      if opt then
        for j:=i+1 to n do
          if opt[j] and (left[j]<right) then
            opt[j]:=false;
  end;
procedure print;
  begin
    for i:=1 to n do
      if opt then
        inc(ans);
    writeln(ans);
    close(output);
  end;
begin
  setio;
  init;
  solve;
  print;
end.

谢谢，共享才能提高