首页 > 代码库 > 1270: [BeijingWc2008]雷涛的小猫
1270: [BeijingWc2008]雷涛的小猫
1270: [BeijingWc2008]雷涛的小猫
Time Limit: 50 Sec Memory Limit: 162 MBSubmit: 905 Solved: 430
[Submit][Status]
Description
Input
Output
Sample Input
Sample Output
8
HINT
Source
题解：额。。这个嘛。。。首先声明——此程序在BZOJ上交每次都莫名其妙的RE，但是我要到数据后在window下测评怎么测都没出问题，额，求各位也帮我找找错。。。好啦，思路如下——这道题是个比较水的DP，就是对于每个树上的点，这个点的可以有两种方式取值——1.直接在同一棵树的正上方一格跳下来。 2.从其他任何树上上方Delta格跳下来。然后当前点的值就是max(正上方,各个其他树上方Delta格)+当前位置的柿子数。。。这么说一个问题出现了——我们需要的是其他树上方的Delta格，不包含自己这个树的，这样子似乎问题处理难度陡增，我甚至想过搬出Splay了。可以再一想发现另一个问题——由于delta>0（phile：题目中不是说的嘛 HansBug：那是那是，假如delta=0的话那岂不是所有的柿子都能随便吃光了啊= =），所以很容易证明对于同一棵树，处于下方的点不可能比处于上方的点求出的结果小，也就是说对于同一棵树上上方delta位置的值即使算入那个高度的max值内，也不会对结果构成任何影响——显然，上方delta的位置连正上方一格的位置都超不过，那有和没有真心差不多啊。。。别的没了。。。
1 var 2 i,j,k,l,m,n,t:longint; 3 ll:int64; 4 a,b:array[0..2500,0..2500] of int64; 5 c:array[0..10000] of int64; 6 function max(x,y:int64):int64;inline; 7 begin 8 if x>y then max:=x else max:=y; 9 end;10 11 begin12 fillchar(a,sizeof(a),0);13 fillchar(b,sizeof(b),0);14 fillchar(c,sizeof(c),0);15 read(n,m,t);16 for i:=1 to n do17 begin18 read(l);19 for j:=1 to l do20 begin21 read(k);22 inc(a[i,k]);23 end;24 end;25 ll:=0;26 for i:=m downto 1 do27 begin28 c[i]:=0;29 for j:=1 to n do30 begin31 b[j,i]:=max(b[j,i+1],c[i+t])+a[j,i];32 c[i]:=max(c[i],b[j,i]);33 ll:=max(b[j,i],ll);34 end;35 end;36 writeln(ll);37 end.
1270: [BeijingWc2008]雷涛的小猫
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。