问题标题: 酷町堂:1535 猴哥吃蟠桃

0
0
已解决
程之行
程之行
高级守护
高级守护

话说孙悟空被玉皇大帝派去掌管蟠桃园,却万万没想到猴哥会偷吃蟠桃,这才引起了后面的猴哥大闹天宫。 假设蟠桃园有M个区间,每个区间由一对整数s-t编号,所以蟠桃园M个区间可用1到N编号,其中1<s<t<N,区间的长度对应蟠桃的个数,猴哥可以任意选择区间进行偷吃蟠桃,但是选择的区间不可以有重叠,现在对于给定的一些区间,请你设计程序建议猴哥找一些空间,使得猴哥偷吃的蟠桃数目达到最多。 例如:有以下3个区间1-3、3-4、7-8,这时1-3和3-4的区间是重叠的,你可以建议猴哥选择1-3和7-8的区间,这样的区间可以吃到5个蟠桃。

输入描述 Input Description

 

type people=record
    s:longint;
    e:longint;
end;
var
    a:array [1..200] of people;
    i,n,j,w,m,ans,h,l,x:longint;
function cmp(x,y:people):longint;
begin
  if x.e < y.e then exit(-1);
  if x.e >y.e then exit(1);
  if x.s > y.s then exit(-1);
  if x.s < y.s then exit(1);
  exit(0);
end;

procedure qsort(l,r:longint);
var
  i,j:longint;
  mid,p:people;
begin
  i:=l; j:=r;
  mid:=a[(l+r) div 2];
  repeat
    while cmp(a[i],mid)<0 do inc(i);
    while cmp(mid,a[j])<0 do dec(j);
    if i<=j then
    begin
      p:=a[i]; a[i]:=a[j]; a[j]:=p;
      inc(i); dec(j);
    end;
  until i>j;
  if l<j then qsort(l,j);
  if i<r then qsort(i,r);
end;
begin
  ans:=0;
  readln(n);
  for i:=1 to n do
    read(a[i].s,a[i].e);
  qsort(1,n);
  x:=0;
  for i:=1 to n do
  begin
    if a[i].s>x then 
    begin 
      x:=a[i].e;
      ans:=ans+(a[i].e-a[i].s)+1;
    end;
  end;
  writeln(ans);
end.

为什么错了


1
已采纳
贾文卓
贾文卓
高级光能
高级光能

这道题目是动态规划,不是一个排序就能搞定的。它要求的答案是选择区间中最多有多少个蟠桃,而不是最多能选择多少个区间。

1
夏子健
夏子健
初级光能
初级光能

 for(int i=1; i<=ans; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(b[j]>i) continue;
            f[i]=max(f[i],f[a[j]-1]+b[j]-a[j]+1);
        }
    }
前面定义一个ans,为最大值

0
我要回答