bzoj1037: [ZJOI2008]生日聚会Party

Dp[i][j][k1][k2]表示前i个人，有j个男孩，从后往前，男孩最多比女孩多k1个，女孩最多比男孩多k2个的方案数

Dp[Now][j + 1][k1 + 1][max(k2 - 1, 0)] += Dp[Last][j][k1][k2]

Dp[Now][j][max(k1 - 1, 0)][k2 + 1] += Dp[Last][j][k1][k2]

const int N = 160, K = 25, Mod = 12345678;
int n, m, k, Dp[2][N][K][K];

inline void Input() {
	scanf("%d%d%d", &n, &m, &k);
}

inline void Add(int &a, int x) {
	a = (a + x) % Mod;
}
inline void Solve() {
	int Now = 0, Last = 1;
	Dp[Now][0][0][0]=1;
	Rep(i, n + m) {
		swap(Now, Last);
		clr(Dp[Now], 0);
		For(j, 0, min(i, n))
			For(k1, 0, min(j, k))
				For(k2, 0, min(i - j, k)) {
					int T = Dp[Last][j][k1][k2];
					if(k1 < k && j < n) Add(Dp[Now][j + 1][k1 + 1][max(k2 - 1, 0)], T);
					if(k2 < k && i - j < m) Add(Dp[Now][j][max(k1 - 1, 0)][k2 + 1], T);
				}
	}
	
	LL Ans = 0;
	For(k1, 0, k)
		For(k2, 0, k) Ans = Ans + Dp[Now][n][k1][k2];
	cout << (Ans % Mod) << endl;
}

int main() {
	Input();
	Solve();
	return 0;
}

 听人说，这题常数优化有很大作用