|
|
思路：
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;
}
|