开心农场(happyfarm.pas/c/cpp)

时间:2023-01-01 04:01:52

【问题描述】
这个夏天,与众不同。QQ空间也引入了最近流行的社区交互类游戏《开心农场》。自然而然地,Chroi也成为了众多农场主的一员。可是Chroi整个暑假忙于OI,没什么时间照顾农场,这就需要你的帮助了。他可以告诉你他每天那些时间可以上线,你要做的就是告诉他该天最多可赚多少钱(为了降低难度,假设腾讯每天晚上0:00清空还没收获的作物,而且由于Chroi的农场等级比较低,所以只能种单季作物(就是只能收获一次的))。
在开心农场中,每个用户都有一定数目的土地,每次上线可以做的事是在土地上摘果实、卖果实、种下种子,每块土地上只能种一种作物,每块土地各自独立。
假设Chroi每次只能上线1秒,他能在瞬间做完所有他想做的事,所以你的程序要在一秒内得出结果。
而且如果Chroi在一天的最后时刻上线,那他此刻做的事算第二天的。(比如时间为24,那他在24时刻做的事算第二天的0时刻做的。)
【输入】(happyfarm.in)
输入文件包含多行,第一行有四个正整数n,m,t,k,分别表示Chroi的农场中有n块地,共有m种作物
可以选择,一天的时间t,有k个时刻Chroi可以上线。

接下来的m 行每行输入三个正整数,第一个数字表示种子价格,第二个数字表示种子成熟时间(小于t),第三个数字表示成熟后果实的售价。再次提示,这些都是整数。
再接下来的一行有k个自然数,保证该整数为0,1,2...t-1中的一个,为Chroi可以上线的时间。这k个自然数不会重复。
输入文件到此结束。
【输出】(happyfarm.out)
输出文件只有一个整数,表示Chroi每天可以获得的最大金钱数。
【样例输入1】
6 3 24 4
10 6 20
15 3 18
11 3 19
0 6 12 18
【样例输出1】
180(共种了3次第一种作物,每次种6块土地,收获了3次,每次收获6块土地,最后一次上线18
的时候只收获,不种植(之后不能再收获,再种植没时间收获,只能亏钱))
【样例输入2】
1 1 24 2
10 6 5
0 6
【样例输出2】
0(种第一种作物还亏钱,不如不种)
【数据范围】
对于30%的数据,0<n<=10,0<m<=50,0<k<=t<=50。
对于50%的数据,0<n<=20,0<m<=500,0<k<=t<=500。
对于100%的数据,0<n<=50,0<m<=3000,0<k<=t<=3000,最后输出的数<maxlongint。

题解: 

f[i]:=Max(f[i],v[OL[i]-OL[j]]+f[j]);//OL上线时刻,v[i]花费i时间得到的最大价值

Function Max(a,b:longint):longint; Begin if a<b Then Exit(b) Else Exit(a); End;
Var
  w,Tt,Vv,DA,n,m,t,k:longint;
  f,v,OL:Array[0..3001] of longint;
  i,j,l:longint;
Procedure qSort(l,r:longint);
  Var
    i,j,Tmp,Mid:longint;
  Begin
    i:=l;
    j:=r;
    Mid:=OL[(l+r) Shr 1];
    Repeat
      While OL[i]<Mid Do inc(i);
      While Mid<OL[j] Do Dec(j);
      if i<=j then
        Begin
          Tmp:=OL[i];
          OL[i]:=OL[j];
          OL[j]:=Tmp;
          inc(i);
          Dec(j);
        End;
    Until i>j;
    if i<r Then qSort(i,r);
    if l<j Then qSort(l,j);
  End;
Begin
  Assign(input,'happyfarm.in');
  ReSet(input);
  Assign(output,'happyfarm.out');
  ReWrite(Output);
  Read(n,m,t,k);
  For i:=1 to m do
    Begin
      Read(w,Tt,Vv);
      if Vv-w>v[Tt] Then v[Tt]:=Vv-w;
    End;
  For i:=1 to k do Read(OL[i]); qSort(1,k);
  For i:=1 to T-1 do if V[i]<v[i-1] Then v[i]:=v[i-1]; //求得需i时间的最大价值
  For i:=2 to k do
    Begin
      f[i]:=0;
      For j:=1 to i-1 do
        f[i]:=Max(f[i],v[OL[i]-OL[j]]+f[j]);
    End;
  DA:=f[k]*n;
  Writeln(DA);
  Close(input);
  Close(output);
End.