Codeforces 478D Red-Green Towers dp
題目鏈接:點擊打開鏈接
題意:
給定r個紅色正方體,g個綠色正方體。
要求搭建一個高度為n的塔。
對於高度為n的塔,第一層積木個數必須為n,第二層必須為n-1,依次類推,每層比下面那層少一個。
且同一層顏色必須相同。
問:
我們設最高能搭建的塔的高度為h,問有多少種方法能搭建出高度為h的塔。
思路:
從最頂層開始構造。
設dp[i][j]表示前i層花了j個紅色木塊的方法數
因為每層的個數固定,所以知道花費紅色的個數,則就能馬上算出花費綠色的個數。
而且對於最高的高度,是和顏色無關的,只和r+g有關,YY得證。
或者直接dp上去,當這一次的方案數是0時,則上一次就是最高的高度了。
前i層可以用滾動數組優化掉。
#include
#include
#include
#include
#include
#include