|
|
思路：
f[a][b] = { 种类数目为 a，蚂蚁数目为 b 时候的方案总数 }
转移：
f[a][b] = f[a - 1][0] + f[a - 1][1] + ... + f[a - 1][b]
时间 O(AT) 如果求 f[a][*] 只用一次循环的话
可以用循环数组
杯具：
把i看成j了，足足调了3个小时，注意，是不吃不喝，也没有上厕所，没有听歌，没有看优酷。。
是精神高度集中地浪费了3个小时！
与非主流之脑残相比，有过之而无不及也。
 #include <stdio.h>
#define P 1000000
int T, A, S, B, fam[1024], dp[2][1024*128], *cur, *pre;
inline int min(int a, int b)
   {
 return a < b ? a : b;
 }
int main()
{
int i, j, cnt, end, sum;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d%d", &T, &A, &S, &B);
  for (i = 0; i < A; i++) {
scanf("%d", &j);
fam[j]++;
 }
for (i = 0; i <= fam[1]; i++)
dp[1][i] = 1;
end = fam[1];
for (i = 2; i <= T; i++) {
cur = dp[i & 1];
pre = dp[(i+1) & 1];
cur[0] = pre[0];
end += fam[i];
for (j = 1; j <= end; j++) {
cur[j] = cur[j - 1] + pre[j];
if (j > fam[i])
cur[j] -= pre[j - fam[i] - 1];
cur[j] += P;
cur[j] %= P;
}
}
sum = 0;
for (i = S; i <= B; i++) {
sum += cur[i];
sum %= P;
}
printf("%d\n", sum);
return 0;
}
|