Codeforces 478D Red-Green Towers

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

思路:dp:f[i][j]代表当前第i层,用了j个绿色方块的方案数,用滚动数组,还有,数组清零的时候一定要用memset,不然for的常数太大。。

 #include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
const int Mod=;
int n,m,sum[],f[][];
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
int main(){
n=read();m=read();
for (int i=;i<=;i++)
sum[i]=sum[i-]+i;
f[][]=;
int i;
for (i=;;i++){
if (sum[i]>n+m) break;
memset(f[i%],,sizeof f[i%]);
for (int j=;j<=sum[i]&&j<=m;j++){
if (sum[i]-j<=n) (f[i%][j]+=f[(i-)%][j])%=Mod;
if (sum[i]-j<=n&&j>=i) (f[i%][j]+=f[(i-)%][j-i])%=Mod;
}
}
int ans=;
for (int j=;j<=m;j++)
ans=(ans+f[(i-)%][j])%Mod;
printf("%d\n",ans);
return ;
}
上一篇:LevelDb系列之简介


下一篇:CentOS6.5yum配置本地源