Poj 3181: Dollar Dayz

poj3181.md

Poj 3181: Dollar Dayz

題目

分析

背包。且要使用大數。

參這

###定義

int dp[i][w] = 使用第 1 個 ~ 第 i 種工具組出 w 元的方法數

答案為 dp[N][K] 實作時，為方便，捨棄 dp[0] 不用。

轉移方程式

dp[i][w] = sum(dp[i - 1][w - i * n] | w - i * n >= 0 | n >= 0)

即為

dp[i][w] = dp[i-1][w] + dp[i-1][w - i] + dp[i-1][w - 2*i] + ... + dp[i-1][0]

因為

dp[i][w - i] = dp[i-1][w] + dp[i-1][w - 2*i] + ... + dp[i-1][0]

所以

dp[i][w] = dp[i-1][w] + dp[i][w-i]

初使條件

dp[0][0] = 1

大數

這題有大數，但使用兩個 unsigned long long 就可以了。

AC Code

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

typedef pair<unsigned long long, unsigned long long> pll; // <high, low>
const unsigned long long M = 1e17;

int N, K;
pll dp[100 + 1][1000 + 1];

pll solve() {
    // dp[i][w] = 使用第 1 個 ~ 第 i 種工具組出 w 元的方法數
    // dp[i][w] = sum(dp[i - 1][w - i * n] | w - i * n >= 0 | n >= 0)
    // 使用 n 個 第 i 種工具
    // 優化過：dp[i][w] = dp[i][w - i] + dp[i-1][w]

    dp[0][0].first = 0;
    dp[0][0].second = 1;
    for (int i = 1; i <= K; i++) {
        for (int w = 0; w <= N; w++) {
            // dp[i][w] = dp[i][w - i] + dp[i-1][w];
            if (w - i < 0) {
                dp[i][w].first = dp[i-1][w].first;
                dp[i][w].second = dp[i-1][w].second;
            }
            else {
                dp[i][w].first = dp[i][w-i].first + dp[i-1][w].first;
                dp[i][w].second = dp[i][w-i].second + dp[i-1][w].second;
                dp[i][w].first += dp[i][w].second / M;
                dp[i][w].second %= M;
            }
        }
    }

    return dp[K][N];
}

int main() {
    cin >> N >> K;
    pll result = solve();
    if (result.first != 0)
        cout << result.first;
    cout << result.second << endl;

    return 0;
}


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;
}