給定紅綠兩種方塊，要求以1，2，3..n的方式，一層一層壘上去，且任意一層只能是單色，問在該種方式下壘到最高高度的方式有多少種？

題意：

???? 給定紅綠兩種方塊，要求以1，2，3..n的方式，一層一層壘上去，且任意一層只能是單色，問在該種方式下壘到最高高度的方式有多少種？

解題：

???? 因為是1，2，3..所以只要剛剛好方塊夠到某一層的總數(shù)量的話，是一定可以構造出可行方案的，因此可以直接根據兩種方塊數(shù)量總和，先求出最高高度。根據范圍，最高高度為1000。可以比較輕松地想到用dp[i][j]來表示，其中i為第幾層,j為到該層為止用了多少紅色方塊，dp的值的含義是在第i層用了j塊紅色方塊的方案數(shù)。此方法看似可行，實則不然，1000*（2*10^5）遠超出題目給的空間限定范圍，且復雜度也夠嗆。因為，我們最后要取的僅僅是最后一層的結果，前面的計算過程都是不需要的，因此，我們可以采用滾動數(shù)組的方法，將第一維壓縮至2，分別表示上一層和下一層。在計算過程中用隊列或其他數(shù)據結構保存要更新的點。最后取最后一層的所有結果和即可。

代碼：

#include#include#include#include#include#include#include#include#define?LL?long?long
#define?maxn?200010
#define?sq(a)??1LL*(a)*(a)
#define?mod?1000000007
using?namespace?std;
bool?vis[maxn];
vectorv[2];
int?amount[1000];
int?dp[2][maxn];
void?init()
{
	for(int?i=1;i0)
	{
		dp[0][0]=1;
		v[0].push_back(0);
	}
	if(r>0)
	{
		dp[0][1]=1;
		v[0].push_back(1);
	}

	a=0;
	b=1;
	for(int?i=2;i<=h;i++)
	{
	???sz=v[a].size();
	???for(int?i=0;i<sz;i++)
		???vis[v[a][i]]=0;
	???for(int?j=0;j<sz;j++)
	???{

		???tmp=amount[i]-v[a][j];
		???if(tmp<=g)
		???{
			???if(!vis[v[a][j]])
			???{
				???v[b].push_back(v[a][j]);
				???dp[b][v[a][j]]=0;
				???vis[v[a][j]]=1;
			???}
			???dp[b][v[a][j]]=(dp[b][v[a][j]]+dp[a][v[a][j]])%mod;
		???}
		???tmp=v[a][j]+amount[i]-amount[i-1];
???????????if(tmp<=r)
		???{
			???if(!vis[tmp])
			???{
				???v[b].push_back(tmp);
				???vis[tmp]=1;
				???dp[b][tmp]=0;
			???}
			???dp[b][tmp]=(dp[b][tmp]+dp[a][v[a][j]])%mod;
		???}
		?}
	???v[a].clear();
	???swap(a,b);
	}
	sz=v[a].size();
	for(int?i=0;i<sz;i++)
		ans=(ans+dp[(h+1)%2][v[a][i]])%mod;
	printf("%dn",ans);
	return?0;
}