1270: [BeijingWc2008]雷濤的小貓

Time Limit:?50 Sec??Memory Limit:?162 MB
Submit:?905??Solved:?430
[Submit][Status]

Description

?

Input

Output

Sample Input

Sample Output

8

HINT

Source

?

題解：額。。這個(gè)嘛。。。首先聲明——此程序在BZOJ上交每次都莫名其妙的RE，但是我要到數(shù)據(jù)后在window下測評怎么測都沒出問題，額，求各位也幫我找找錯。。。好啦，思路如下——這道題是個(gè)比較水的DP，就是對于每個(gè)樹上的點(diǎn)，這個(gè)點(diǎn)的可以有兩種方式取值——1.直接在同一棵樹的正上方一格跳下來。 2.從其他任何樹上上方Delta格跳下來。然后當(dāng)前點(diǎn)的值就是max(正上方,各個(gè)其他樹上方Delta格)+當(dāng)前位置的柿子數(shù)。。。這么說一個(gè)問題出現(xiàn)了——我們需要的是其他樹上方的Delta格，不包含自己這個(gè)樹的，這樣子似乎問題處理難度陡增，我甚至想過搬出Splay了。可以再一想發(fā)現(xiàn)另一個(gè)問題——由于delta>0（phile：題目中不是說的嘛 HansBug：那是那是，假如delta=0的話那豈不是所有的柿子都能隨便吃光了啊= =），所以很容易證明對于同一棵樹，處于下方的點(diǎn)不可能比處于上方的點(diǎn)求出的結(jié)果小，也就是說對于同一棵樹上上方delta位置的值即使算入那個(gè)高度的max值內(nèi)，也不會對結(jié)果構(gòu)成任何影響——顯然，上方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 begin 12 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 do 17 begin 18 read(l); 19 for j:=1 to l do 20 begin 21 read(k); 22 inc(a[i,k]); 23 end; 24 end; 25 ll:=0; 26 for i:=m downto 1 do 27 begin 28 c[i]:=0; 29 for j:=1 to n do 30 begin 31 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.

?

轉(zhuǎn)載于:https://www.cnblogs.com/HansBug/p/4175611.html

總結(jié)

以上是生活随笔為你收集整理的1270: [BeijingWc2008]雷涛的小猫的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。