给定红绿两种方块，要求以1，2，3..n的方式，一层一层垒上去，且任意一层只能是单色，问在该种方式下垒到最高高度的方式有多少种？

题意：

     给定红绿两种方块，要求以1，2，3..n的方式，一层一层垒上去，且任意一层只能是单色，问在该种方式下垒到最高高度的方式有多少种？

解题：

     因为是1，2，3..所以只要刚刚好方块够到某一层的总数量的话，是一定可以构造出可行方案的，因此可以直接根据两种方块数量总和，先求出最高高度。根据范围，最高高度为1000。可以比较轻松地想到用dp[i][j]来表示，其中i为第几层,j为到该层为止用了多少红色方块，dp的值的含义是在第i层用了j块红色方块的方案数。此方法看似可行，实则不然，1000*（2*10^5）远超出题目给的空间限定范围，且复杂度也够呛。因为，我们最后要取的仅仅是最后一层的结果，前面的计算过程都是不需要的，因此，我们可以采用滚动数组的方法，将第一维压缩至2，分别表示上一层和下一层。在计算过程中用队列或其他数据结构保存要更新的点。最后取最后一层的所有结果和即可。

代码：

#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;
}