BZOJ2023: [Usaco2005 Nov]Ant Counting 數螞蟻(dp)

題意

題目描述的很清楚。。。

 有一天，貝茜無聊地坐在螞蟻洞前看螞蟻們進進出出地搬運食物．很快貝茜發現有些螞蟻長得幾乎一模一樣，於是她認為那些螞蟻是兄弟，也就是說它們是同一個家族裡的成員．她也發現整個螞蟻群里有時只有一隻出來覓食，有時是幾隻，有時乾脆整個蟻群一起出來．這樣一來，螞蟻們出行覓食時的組隊方案就有很多種．作為一頭有數學頭腦的奶牛，貝茜註意到整個螞蟻群由T(1≤T≤1000)個家族組成，她將這些家族按1到T依次編號．編號為i的家族裡有Ni(1≤Ni≤100)只螞蟻．同一個家族裡的螞蟻可以認為是完全相同的．     如果一共有S，S+1…．，B(1≤S≤B≤A)只螞蟻一起出去覓食，它們一共能組成多少種不同的隊伍呢？註意：只要兩支隊伍中所包含某個家族的螞蟻數不同，我們就認為這兩支隊伍不同．由於貝茜無法分辨出同一家族的螞蟻，所以當兩支隊伍中所包含的所有家族的螞蟻數都相同時，即使有某個家族換了幾隻螞蟻出來，貝茜也會因為看不出不同而把它們認為是同一支隊伍．   

Sol

裸的dp比較好想，$f[i][j]$表示前$i$個家族，選了$j$個螞蟻

轉移的時候枚舉這個選了幾個

這玩意兒顯然可以用首碼和優化，空間問題用滾動數組處理

有一個小trick：在處理首碼和的時候我們可以保留下本層dp的信息，所以滾動數組是不需要的，具體看代碼吧

#include<cstdio>
#include<algorithm>
#include<cstring>
#define pt(x) printf("%d ", x);
using namespace std;
const int MAXN = 1e5 + 10, mod = 1000000;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); 
    return x * f;
}
int T, A, L, R;
int num[MAXN], f[MAXN], sum[MAXN], s;
int main() {
    T = read(); A = read(); L = read(); R = read();
    for(int i = 1; i <= A; i++) num[read()]++;
    for(int i = 0; i <= num[1]; i++) sum[i] = 1;
    for(int i = 1; i <= T; i++) {
        s += num[i];    
        for(int j = 0; j <= s; j++) {
            int x = j - num[i] - 1;
            f[j] = sum[j];
            if(x >= 0) f[j] = (f[j] - sum[x] + mod) % mod;
        }    
        sum[0] = f[0];
        for(int j = 1; j <= s + num[i + 1]; j++) 
            sum[j] = (sum[j - 1] + f[j]) % mod;
        if(i != T) memset(f, 0, sizeof(f));
    }
    int ans = 0;
    for(int i = L; i <= R; i++)
        (ans += f[i]) %= mod;
    printf("%d", ans % mod);
    return 0;
}
/*
3 5 1 5
1
2
2
1
3
*/