POJ 3046 DP

题目链接:http://poj.org/problem?id=3046

有 $T$ 个种族的蚂蚁,每个种族有 $N_i$ 只蚂蚁,将一定数量的蚂蚁聚集为一组,问有多少种组法。(不同种族的蚂蚁可以区分,但是相同种族的蚂蚁无法区分)

例如有 $T=3, N_1=2, N_2=2, N_3=1$,将第一种蚂蚁用数字 1 表示,第二种蚂蚁用 2 表示,以此类推,则 $1…5$ 这五种集合大小的方案分别为:

1 ant: {1} {2} {3} 
2 ants: {1,1} {1,2} {1,3} {2,2} {2,3}
3 ants: {1,1,2} {1,1,3} {1,2,2} {1,2,3} {2,2,3}
4 ants: {1,2,2,3} {1,1,2,2} {1,1,2,3}
5 ants: {1,1,2,2,3}

思路

本题可以转化为多重集组合数问题,描述如下:

有 $n$ 种物品,第 $i$ 种物品有 $a_i$ 个,不同种类的物品可以区分,但是相同种类的物品无法区分。现在要从这些物品中取出 $m$ 个,有多少种取法?

定义 $dp[i][j]$ 为前 $i$ 个种类,取出 $j$ 个时的方案数量。

为了从前 $i$ 个种类中取出 $j$ 个,可以从前 $i-1$ 中取出 $j-k$ 个,再从第 $i$ 类中取出 $k$ 个。

$$
dp[i][j] = \sum_{k=0}^{min(a_i, j)}dp[i-1][j-k]
$$

直接计算这个表达式的话,时间复杂度是 $O(nm^2)$,不过由于:

$$
\sum_{k=0}^{min(a_i, j)}dp[i-1][j-k] = \sum_{k=0}^{min(a_i, j-1)}dp[i-1][j-k-1] + dp[i-1][j] - dp[i-1][j-1-a_i]
$$

因此:

$$
dp[i][j] = dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1-a_i]
$$

具体实现中,我们可以使用滚动数组来节省空间:

3046.cppview raw
#include <iostream>
#include <stdio.h>
#define MOD 1000000
#define maxn 1005
#define maxm 100005
using namespace std;

int n, m, st, ed, dp[2][maxm], c[maxn];

int main() {
scanf("%d %d %d %d", &n, &m, &st, &ed);
for (int i = 0; i < m; i++) {
int t;
scanf("%d", &t);
c[t - 1]++;
}
dp[0][0] = dp[1][0] = 1;
for (int i = 0; i < n; i++)
for (int j = 1; j <= m; j++)
if (j - 1 - c[i] >= 0)
dp[i % 2][j] = (dp[i % 2][j - 1]
+ dp[!(i % 2)][j]
- dp[!(i % 2)][j - 1 - c[i]] + MOD) % MOD;
else
dp[i % 2][j] = (dp[i % 2][j - 1]
+ dp[!(i % 2)][j]) % MOD;
int ans = 0;
for (int j = st; j <= ed; j++)
ans = (ans + dp[(n - 1) % 2][j]) % MOD;
printf("%d\n", ans);
return 0;
}