Poj 3046: Ant Counting

poj3046.md

Poj 3046: Ant Counting

題目

分析

也是類背包問題，但變成算方法數。 兩個 Code，第一個是完全照著定義做；第二個是怕會 MLE，改成交互使用 dp 陣列

###定義

int dp[i][w] = 使用第 1 ~ 第 i 個 family 組出 w 的方法數。

答案為 sum([dp[T][x] | S <= x <= B]) 實作時，為方便，捨棄 dp[0] 不用。

轉移方程式

dp[i][w] = sum(dp[i-1][w-k] | 0 <= k <= number[i])

初使條件

dp[1][x] = 1 | 0 <= x <= number[1]

AC Code 1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int T, A, S, B;
const int M = 1000000;

int number[1000 + 1];
int dp[1000 + 1][100000 + 1];

int solve() {
    // dp[i][w] = sum(dp[i-1][w - k] | 0 <= k <= number[i])

    for (int w = 0; w <= number[1]; w++)
        dp[1][w] = 1;

    int ants_cnt = number[1];
    for (int i = 2; i <= T; i++) {
        ants_cnt += number[i];
        for (int w = 0; w <= ants_cnt; w++) {
            dp[i][w] = 0;
            for (int k = 0; k <= number[i] && w - k >= 0; k++) {
                dp[i][w] = (dp[i][w] + dp[i-1][w - k]) % M;
            }
        }
    }

    int cnt = 0;
    for (int i = S; i <= B; i++) {
        // cout << i << ": " << dp[T][i] << endl;
        cnt = (cnt + dp[T][i]) % M;
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);

    cin >> T >> A >> S >> B;
    for (int i = 0; i < A; i++) {
        int family;
        cin >> family;
        number[family]++;
    }

    cout << solve() << "\n";

    return 0;
}

AC Code 2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int T, A, S, B;
const int M = 1000000;

int number[1000 + 1];
// int dp[1000 + 1][100000 + 1];

int dp[2][100000 + 1];
int *cur = dp[0];
int *pre = dp[1];

int solve() {
    // dp[i][w] = sum(dp[i-1][w - k] | 0 <= k <= number[i])

    for (int w = 0; w <= number[1]; w++)
        cur[w] = 1;

    swap(cur, pre);

    int ants_cnt = number[1];
    for (int i = 2; i <= T; i++) {
        ants_cnt += number[i];
        for (int w = 0; w <= ants_cnt; w++) {
            cur[w] = 0;
            for (int k = 0; k <= number[i] && w - k >= 0; k++) {
                cur[w] = (cur[w] + pre[w - k]) % M;
            }
        }
        swap(cur, pre);
    }

    int cnt = 0;
    for (int i = S; i <= B; i++) {
        // cout << i << ": " << dp[T][i] << endl;
        cnt = (cnt + pre[i]) % M;
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);

    cin >> T >> A >> S >> B;
    for (int i = 0; i < A; i++) {
        int family;
        cin >> family;
        number[family]++;
    }

    cout << solve() << "\n";

    return 0;
}