开心农场(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.

 

标签：

相关文章