UVa11832 - Account Book(動態規劃 Dynamic programming)

題目大意

打擊腐敗基金會要對 Nlogonia 非法組織做審查，但基金會收到帳本後卻發現帳本並沒有表示交易紀錄是收入還是支出，只剩下數字、結餘多少。
於是我們希望可以透過程式還原每項明細，他是收入還是支出。

如果此結餘跟所有明細都對不上就輸出 *
如果這筆明細確認是收入就輸出 +
如果這筆明細確認是費用就輸出 -
如果這筆明細無法確認就輸出 ?

題目連結

重點觀念

• 動態規劃 - 大衛的筆記
• 紀錄每一種明細組合的資訊
• 當明細組合與其他明細組合相同時，要如何合併
• 使用動態規劃？還是有辦法貪心嗎？
• 有負數的動態規劃要怎麼樣建立陣列？

分析

好題一題，讓我學了很多東西XD

• 我們可以確定一件事，我們必須追蹤每一個明細在不同組合時的狀態。
• 使用貪心？使用動態規劃？
  • 貪心
    • \(40!= 8.1591528e+47\)，一看就知道不可能
    • 遇到結餘有多種組合時不容易處理。
  • 動態規劃
    • 透過陣列與二進位表達，來結合多種組合
    • 無法確認的狀態就是這筆明細設定為支出時，也可以透過與其他明細組合，變成結餘的數字
      怎麼解決這個問題，我們可以用兩個 DP 陣列(紀錄正、紀錄負)來解決
    • 看起來動態規劃是比較好的方法
• 動態規劃要處理的問題
  • 題目的明細有可能是支出，那假如結餘是負數，我的動態規劃 index 不可以是負數
    題目有說明細最大值是 1000，最多 40 筆，因此我們可以設定 dp 長度為 \(40 * 1000 * 2 = 80000\)，為了保險起見，建議可以開 100000，並以 index 50000 作為結餘 0 的標準，方便邏輯思考
  • 因為我們已經開了一個很大的 dp 陣列，如果我們開一個 dp[明細數量][結餘]，會爆炸，那要怎麼辦
    我們可以了解到，其實我們的 dp 都是根據到dp[上一個明細數量][結餘] 延續的，因為我們每一個名係數都會使用到，只是決定正或負
  • 那我要怎麼在 dp 內存放每筆交易的收入或支出呢？
    透過 2 進位表示，110(2)，表示第二筆第三筆是正的。以此類推
  • 第三點只有提到交易為收入的表達，那支出呢？
    沒辦法，開兩個 dp，分別存放收入交易、支出交易
  • 其他的概念就與 dp 相同，直接看程式碼表達就好。
• 提醒，在使用 2 進位表達時，必須開 long long，因為 \(n=40\)，會過大。
• 一開始必須先將第一筆交易紀錄先額外寫入 dp，不可以讓 dp[上一個明細數量][0] = 1，因為 f 可以是 0。
• 動態規劃邏輯關係表達如下

  int L = 累積交易明細都是支出的結餘
  int R = 累積交易明細都是收入的結餘
  
  for(交易明細){
      for(L~R){ //加速搜尋，以避免需要 0~100000 大量 for
          if(收入交易[上一個交易][結餘] || 支出交易[上一個交易][結餘]){
              收入交易[這一個交易][結餘 + 正交易明細] |=  收入交易[上一個交易][結餘] + 正交易明細
              支出交易[這一個交易][結餘 + 正交易明細] |=  收入交易[上一個交易][結餘] 
              收入交易[這一個交易][結餘 + 負交易明細] |=  收入交易[上一個交易][結餘] 
              支出交易[這一個交易][結餘 + 負交易明細] |=  收入交易[上一個交易][結餘] + 負交易明細
  
              //也就是說當你想看某個結餘時，你必須同時看支出交易、收入交易。
              //支出交易負責 支出明細
              //收入交易負責 收入明細
  
              //注意必須要是 |=，因為如果剛好另種組合也等於結餘時，必須兩種狀態都保存，所以是 or
          }
      }
  }

參考連結

Uva11832 - Account Book by txya900619

心得

這題很不賴欸，開導了我很多東西，很多是我自己沒有學過的一些小伎倆，透過這題來讓自己收穫許多。

並且也了解到有時候並不需要把所有的交易紀錄資訊都放在同個陣列裡，那樣會很難處理。分開來會好很多，只是我不知道當我遇到這種題目時，我有沒有辦法把這些想法都套用在題目上。

希望我都可以套用在題目上，有機會套用在未來上。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
//#define DEBUG
#define MAXN 1020
#define int long long
using namespace std;
int n, f, t;
int add[2][100000]; //收入交易
int subtract[2][100000]; //支出交易
int num[MAXN];

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL

    while(cin >> n >> f && n){
        memset(add, 0, sizeof(add));
        memset(subtract, 0, sizeof(subtract));

        for(int i = 0; i < n; i++) cin >> num[i];

        //roll 只會以 0,1 兩種型態存活，當 roll = 0，那 1 就是當前交易，0 為上一筆，反之亦同
        int L=50000-num[0], R=50000+num[0], roll = 0; 
        add[0][R] = 1; //分析第五點
        subtract[0][L] = 1;

        for(int i = 1; i < n; i++){ //分析第六點
            memset(add[!roll], 0, sizeof(add[!roll]));
            memset(subtract[!roll], 0, sizeof(subtract[!roll]));

            for(int j = L; j <= R; j++){
                if(add[roll][j] || subtract[roll][j]){
                    int add_value = j + num[i];
                    add[!roll][add_value] |= add[roll][j] | (1LL << i);
                    subtract[!roll][add_value] |= subtract[roll][j];

                    int subtract_value = j - num[i];
                    add[!roll][subtract_value] |= add[roll][j];
                    subtract[!roll][subtract_value] |= subtract[roll][j] | (1LL << i);
                }
            }
            L -= num[i]; //區間修改，因為最低結餘與最高結餘的上下限改變了
            R += num[i];
            roll = !roll; //roll 修改，上上一筆明細已經被延續，現在是需要當前明細

            //cout << "roll " << roll << '\n';
        }

        #ifdef DEBUG
        for(int i = L-50000; i <= R-50000; i++) printf("%3d ", i);
        cout << '\n';
        for(int i = L; i <= R; i++) printf("%3d ", add[roll][i]);
        cout << '\n';
        #endif //debug

        f += 50000; //因為我們一開始就加了 50000
        //此結餘跟所有交易中的結餘都沒有任何明細紀錄
        if(add[roll][f] == 0 && subtract[roll][f] == 0){ 
            cout << "*" << "\n";
            continue;
        }
        for(int i = 0; i < n; i++){
            int item = 1LL << i; //2進位筆達
            if(add[roll][f] & item){ //收入紀錄
                if(subtract[roll][f] & item) cout << "?"; //收入跟支出都有此紀錄
                else cout << "+" ;
            }
            else if(subtract[roll][f] & item) cout << "-"; //支出紀錄
        }
        cout << "\n";

    }
    return 0;
}