学步园

比较简单的DP，关键是设计好状态。

使用f[i][j][p1][p2]表示前i个小孩中有j个男孩，且男孩比女孩多p1个，女孩比男孩多p2个的方案数

根据当前状态累加之后的状态

转移方程:f[i+1][j+1][p1+1][p2-1] =
∑f[i][j][p1][p2],f[i+1][j][p1-1][p2+1] =
∑f[i][j][p1][p2]

由于根据当前状态累加之后的状态，所以要从0开始递推。

注意好边界情况就行了。

代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mo = 12345678;
const int maxn = 152;
const int maxk = 22;
int f[2][maxn][maxk][maxk];
int n,b,g,k;
void init()
{
	freopen("bzoj1037.in","r",stdin);
	freopen("bzoj1037.out","w",stdout);
}

void add(int &a,int b)
{
	a += b;
	if(a >= mo)a -= mo;
}

void readdata()
{
	scanf("%d%d%d",&b,&g,&k);
	n = b + g;
}

void solve()
{
	memset(f,0,sizeof(f));
	int now = 0,las = 1;
	f[0][0][0][0] = 1;
	for(int i = 0;i < n;i++)
	{
		swap(now,las);
		memset(f[now],0,sizeof(f[now]));
		for(int j = 0;j <= min(i,b);j++)
		{
			for(int p1 = 0;p1 <= min(j,k);p1++)
			{
				for(int p2 = 0;p2 <= min((i - j),k);p2++)
				{
					int tmp = f[las][j][p1][p2];
					if(p1 < k && j < b)add(f[now][j+1][p1+1][max(p2-1,0)],tmp);
					if(p2 < k && (i - j) < g)add(f[now][j][max(p1-1,0)][p2+1],tmp);
				}
			}
		}
	}
	int ans = 0;
	for(int p1 = 0;p1 <= k;p1++)
		for(int p2 = 0;p2 <= k;p2++)
			add(ans,f[now][b][p1][p2]);
	printf("%d\n",ans);
}

int main()
{
	init();
	readdata();
	solve();
	return 0;
}