https://codeforces.com/problemset/problem/478/D

題意：

給定r個紅塊，g個綠塊，排列要求：1.第i行放i塊;? ? ?2.每行同色?

問當堆放成最大高度時，有多少種可能的堆放方式?

思路：

首先確定能夠放置幾行

設紅塊有r個，綠塊有g(shù)個，那么放置h行需要(h+1)h/2個

那么r+g>=(h+1)h/2 => 2(r+g)>=(h+1)h => 2(r+g)>h*h

那么有 h=sqrt(2r+2g)，然后再找符合條件的h?

狀態(tài)：dp[i][j]表示前i行用了j個紅塊的排列方案個數(shù)

轉(zhuǎn)移方程：外層循環(huán)枚舉i表示第i層，內(nèi)層循環(huán)枚舉j表示紅塊使用數(shù)?

1. 如果 i<=j，? ? dp[i][j]=dp[i-1][j]+dp[i-1][j-i]，即第i層不用紅塊和全部用紅塊的兩種決策?

2. 如果 i>j， dp[i][j]=dp[i-1][j], 即第i層只能用綠塊

決策合法性：

前i層紅塊至少用max(i(i+1)/2-g,0)個?

初始狀態(tài)，dp=0,

如果r>0,dp[1][1]=1；

如果g>0,dp[1][0]=1?

用滾動數(shù)組優(yōu)化?