Uva11832 - Account Book

題目大意

帳本上有許多條目，但條目上區別是收入還是支出的部分被塗掉了，所以我們需要找出可以確定哪幾條是收入還是支出並輸出出來(會給予最後的餘額)

重點觀念

• 應該算 dp + 二進制?
• 參考 https://github.com/morris821028/UVa/blob/master/volume118/11832 - Account Book2.cpp

分析

• 目標就是將所有加減的可能記錄起來，以 plus[i][j] 來看 i 只是用來區分此輪與下一輪， j 則是代表加到 j 這個數時所有有可能是收入的條目(二進位表示 1 則為有可能 0 為不可能)

程式題目碼

#include <string.h>

#include <iostream>
using namespace std;

int main() {
    int n, f;
    while (cin >> n >> f, n != 0) {
        int a[n], roll = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        long long plus[2][80005];
        long long minus[2][80005];
        memset(plus, 0, sizeof(plus));
        memset(minus, 0, sizeof(minus));

        plus[roll][40000 + a[0]] = 1;
        minus[roll][40000 - a[0]] = 1;
        int L = -a[0] + 40000;
        int R = a[0] + 40000;

        for (int i = 1; i < n; i++) {
            memset(plus[1 - roll], 0, sizeof(plus[0]));
            memset(minus[1 - roll], 0, sizeof(minus[0]));
            for (int j = L; j <= R; j++) {
                if (plus[roll][j] || minus[roll][j]) {
                    int k = j + a[i];
                    plus[1 - roll][k] |= plus[roll][j] | (1LL << i);
                    minus[1 - roll][k] |= minus[roll][j];
                    k = j - a[i];
                    plus[1 - roll][k] |= plus[roll][j];
                    minus[1 - roll][k] |= minus[roll][j] | (1LL << i);
                }
            }
            L -= a[i];
            R += a[i];
            roll = 1 - roll;
        }

        long long ans_p = plus[roll][f + 40000];
        long long ans_m = minus[roll][f + 40000];
        if (ans_p == 0 && ans_m == 0) {
            cout << "*";
        } else {
            for (int i = 0; i < n; i++) {
                if ((ans_p >> i) & 1) {
                    if ((ans_m >> i) & 1) {
                        cout << "?";
                    } else {
                        cout << "+";
                    }
                } else {
                    cout << "-";
                }
            }
        }
        cout << endl;
    }

    return 0;
}