有個(gè)牛，好多題了，都是牛。然后她想吃蘋果。有兩個(gè)樹，單位時(shí)間，在一棵樹上會(huì)掉下來一個(gè)蘋果。她必須在這個(gè)時(shí)間正好站到了這棵樹下，才能吃到這個(gè)蘋果。現(xiàn)在給你一共有T（1000）個(gè)單位時(shí)間，以及每個(gè)單位時(shí)間是哪一顆樹上要掉蘋果，這個(gè)牛可以瞬間從一棵樹到達(dá)另一棵樹下面，但是這種瞬移技能只能釋放最多w（30）次 。問你這個(gè)牛最多可以吃到多少蘋果。（注：牛一開始在1號(hào)樹下）ps:要是問西瓜就好了，因?yàn)槲鞴喜婚L在樹上···· 

思路：

設(shè)a[i][j][k]表示這個(gè)牛在第i個(gè)蘋果掉下來時(shí)，在j號(hào)樹下，用了k次技能，所能得到的最多的蘋果數(shù)。

遞推公式：a[i][j][k]=max(a[i-1][j][k],a[i-1][!j][k-1]); if(v[i]==j)a[i][j][k]++;邊界條件：a[1][j][k]；a[i][j][0]；

關(guān)于遞推公式以及邊界條件的解釋：

這個(gè)牛在第i個(gè)蘋果掉下來的時(shí)候，在第j號(hào)樹下，用了k次技能。能得到這個(gè)狀態(tài)的上一狀態(tài)為：這個(gè)牛在第i-1個(gè)蘋果掉下來的時(shí)候，在第！j號(hào)樹下，用了k-1次技能；或者這個(gè)牛在第i-1個(gè)蘋果掉下來的時(shí)候，在第j號(hào)樹下，用了k次技能。（關(guān)鍵也就是這個(gè)牛在第i-1個(gè)蘋果掉下來和第i個(gè)蘋果掉下來之間，有沒有使用技能）然后如果，這個(gè)蘋果他接到了，就+1唄~

然后是關(guān)于邊界條件，很適合想想一個(gè)三維的表格來儲(chǔ)存數(shù)組a（雖然想畫個(gè)三維圖，但是用筆畫的圖爛的掉渣，估計(jì)大家也看不清，就自己想象吧），這樣的話，如果要推出第i層的一個(gè)，就需要知道第i-1層的兩個(gè)格（沿i軸-1的一個(gè)，以及同i-1平面內(nèi)無相交邊的另一個(gè)）。這樣，在i取1的時(shí)候，就找不到對(duì)應(yīng)的i-1平面了，所以要確定邊界a[1][j][k]；同樣，在k=0時(shí)就找不到對(duì)應(yīng)的k-1了，所以也要確定邊界a[i][j][0]。另外十分要注意，開始的時(shí)候在1號(hào)樹下面，所以一切在2號(hào)數(shù)下面翻轉(zhuǎn)0次得到的蘋果數(shù)都是-inf。 

然后三層循環(huán)為什么從外到內(nèi)的順序?yàn)閕kj:還是有些疑問，不過目前對(duì)于這道題來看，調(diào)換ik的內(nèi)外層關(guān)系并沒有發(fā)生錯(cuò)誤。對(duì)于三維圖來說，只不過是改變了各個(gè)格的數(shù)值確定的順序。然后就是對(duì)遞推公式理解上就不太好解釋了(其實(shí)也是可以解釋的):一個(gè)一個(gè)的用技能，在第i個(gè)格用技能得到的總金額可以根據(jù)在第i-1個(gè)格用技能（a[i-1][j][k]）或者不用這個(gè)技能（a[i-1][!j][k-1]） 兩種情況來確定。