http://codeforces.com/problemset/problem/478/D
思路:dp：f[i][j]代表当前第i层，用了j个绿色方块的方案数，用滚动数组，还有，数组清零的时候一定要用memset，不然for的常数太大。。
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #include<cstring> 5 #include<iostream> 6 const int Mod=1000000007; 7 int n,m,sum[200005],f[3][200005]; 8 int read(){ 9 int t=0,f=1;char ch=getchar(); 10 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} 11 while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} 12 return t*f; 13 } 14 int main(){ 15 n=read();m=read(); 16 for (int i=1;i<=1000;i++) 17 sum[i]=sum[i-1]+i; 18 f[0][0]=1; 19 int i; 20 for (i=1;;i++){ 21 if (sum[i]>n+m) break; 22 memset(f[i%2],0,sizeof f[i%2]); 23 for (int j=0;j<=sum[i]&&j<=m;j++){ 24 if (sum[i]-j<=n) (f[i%2][j]+=f[(i-1)%2][j])%=Mod; 25 if (sum[i]-j<=n&&j>=i) (f[i%2][j]+=f[(i-1)%2][j-i])%=Mod; 26 } 27 } 28 int ans=0; 29 for (int j=0;j<=m;j++) 30 ans=(ans+f[(i-1)%2][j])%Mod; 31 printf("%d ",ans); 32 return 0; 33 }