Codeforces Round #273 (Div. 2) D. Red-Green Towers dp+滚动数组

D Red-Green Towers

题意：有红绿两色的方块，数量分别为r个和g个。有0<=r,g<=2e5，r+g>=1，我们想用这红绿两色的方块（不一定全部，可以是一部分），构成一个高度尽可能高的积木块。

这个积木块需要满足——

1. 假设高度为h，那么第一层有1个，第二层有2个，……，第h层有h个。
2. 每层方块的颜色，不是全部为红色，就是全部为绿色。

让你输出，有多少种方案，可以构成高度最高的积木块

分析：先算出塔的高度h，用dp[i][j]表示0~i层使用j个红色积木块的方案数，很容易得到状态转移方程

dp[i][j]=d[i-1][j]+d[i-1][j-i] ，但是开不出这么大的数组，因为状态转移时只需要前一层的状态，所以只需要用一个一维数组 dp[j]=dp[j]+dp[j-i] ,状态转移时需要从r——>i，否则i-1层状态会被i层状态替换 eg:0层-->1层 dp[2]=dp[2]+dp[2-1] dp[3]=d[3]+dp[3-1] 第二转移方程个中dp[2]不是第0层状态，而是第一个状态转移方程中所得第1层状态dp[2]，将两个状态转移方程顺序改变就不会出现这种问题。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
const int MOD=1e9+7;

int r,g;
int dp[N]={0};
int h;
int main(){
	cin>>r>>g;
	h=sqrt( (r+g)*2 );
	if( h*(h+1)/2>(r+g) ) h--;
	dp[0]=1;
	for(int i=1;i<=h;i++){
		for(int j=r;j>=i;j--){
			dp[j]=(dp[j]+dp[j-i])%MOD;
		}
	}
	int ans=0;
	for(int i=max(h*(h+1)/2-g,0);i<=r;i++){
		ans=(ans+dp[i])%MOD;
	}
	cout<<ans<<endl;
	return 0;
}