https://vjudge.net.cn/problem/POJ-3046#author=GPT_zh
有一天，贝西在蚂蚁山里探头探脑，看着蚂蚁们来来回回地觅食。
她发现很多蚂蚁都是兄弟姐妹，彼此无法区分。
她还发现，有时只有一只蚂蚁去觅食，有时几只，有时全部。
这就产生了大量不同组合的蚂蚁！
有点数学天赋的贝茜开始琢磨起来。贝西注意到，蜂巢里有 T（1 <= T <= 1,000）个蚂蚁家庭，
她把它们标为 1...T（共有 A 只蚂蚁）。
每个家庭有一定数量的蚂蚁 Ni (1 <= Ni <= 100)。
可以组成多少个大小为 S、S+1、......、B（1 <= S <= B <= A）的小组？
在观察一个蚂蚁群时，可以看到三个蚂蚁家族的集合是{1, 1, 2, 2, 3}，但很少按这个顺序排列。
蚂蚁行进的可能集合是
有 1 只蚂蚁的 3 个集合： {1} {2} {3}
有 2 只蚂蚁的 5 组 {1,1} {1,2} {1,3} {2,2} {2,3}
有 3 只蚂蚁的 5 组 {1,1,2} {1,1,3} {1,2,2} {1,2,3} {2,2,3}
有 4 只蚂蚁的 3 组 {1,2,2,3} {1,1,2,2} {1,1,2,3}
有 5 只蚂蚁的 1 组 {1,1,2,2,3}
你的任务是根据上述数据计算可能的蚂蚁集合数。
输入
* 第 1 行：4 个空格分隔的整数： T、A、S 和 B
* 第 2...A+1 行：每行包含一个整数，即蜂巢中存在的蚂蚁类型
输出
* 第 1 行： 可创建的大小为 S...B（包括 S...B）的集合数量。像 {1,2} 这样的集合与 {2,1} 这样的集合相同，不应重复计算。
只打印该数字的后六位，不打印前导零或空格。
3 5 2 3
1
2
2
1
3
10
提示
输入细节：
三种类型的蚂蚁（1...3）；共有 5 只蚂蚁。可以制作多少套大小为 2 或 3 的蚂蚁？
输出细节：
5 组有两名成员的蚂蚁；另外 5 组有三名成员的蚂蚁
解答
dp
代码如下:
#include <iostream>
using namespace std;
const int N = 1000 * 100 + 10;
int dp[1000][N];
int ants[N];
int T, S, A, B;
const int MOD = 1000000;
void solve() {
dp[0][0] = 1;
for (int i = 1; i <= T; i++) {
for (int j = 0; j <= A; j++) {
for (int k = 0; k <= ants[i]; k++) {
if (j >= k) {
dp[i][j] += dp[i - 1][j - k];
dp[i][j] %= MOD;
}
}
}
}
long long ans = 0;
for (int i = S; i <= B; i++) {
ans += dp[T][i];
ans %= MOD;
}
cout << ans << endl;
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> T >> A >> S >> B;
for (int i = 1; i <= A; i++) {
int t; cin >> t;
ants[t]++;
}
solve();
return 0;
}
在POJ能ac 但是可能是数据太弱的原因。
A在极端取值 1000组蚂蚁 每个蚂蚁都是100个。 那么A=100000
上面的代码 耗时就是O(AT100) 就是1e10 会超时的。
下面进行优化
#include <iostream>
using namespace std;
const int N = 1000 * 100 + 10;
int dp[1000][N];
int ants[N];
int T, S, A, B;
const int MOD = 1000000;
void solve() {
dp[0][0] = 1;
for (int i = 1; i <= T; i++) {
for (int j = 0; j <= A; j++) {
if (j == 0) { dp[i][j] = 1; }
else if (j >= ants[i]+1) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - ants[i]-1];
}
else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
dp[i][j] %= MOD;
}
}
long long ans = 0;
for (int i = S; i <= B; i++) {
ans += dp[T][i];
ans = (ans + MOD) % MOD;
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> T >> A >> S >> B;
for (int i = 1; i <= A; i++) {
int t; cin >> t;
ants[t]++;
}
solve();
return 0;
}