Q3-我是股神

2022.11.12 PM 03:00 by CBJ

來源 : 111資訊學科能力競賽複賽-彰雲嘉
標籤 : 暴力法(遞迴)
難易度 : 3

題目敘述 ： 
你被賦予一個看見未來的超能力，可以看到未來m天A,B兩個公司的股價，你必須買低賣高來賺取價差，而總利潤則是每個價差的總和，請求出最大利潤。
(注：同一天最多只能有一張股票(A or B))
對於每天，若持有股票，可選擇賣或不賣
若沒有股票，可選擇買A or B股票，或不買
(同一天不能同時有買和賣)

輸入說明 ：
第一行會有一個整數m，代表能夠預知到第幾天。
第二行會有m個整數，代表A公司這m天的股價。
第三行也會有m個整數，代表B公司這m天的股價。

範例測資 ： 
範例輸入
9
4 5 7 7 3 8 1 5 10
2 5 6 3 2 2 6 9 7
範例輸出
18

測資說明 ：
對於範例測資的賺錢策略應如下：
第一天買入B股票，價格為2, 第三天賣出得價差為(6-2) = 4, 第五天買入A股票，價格為3, 第六天賣出得價差為(8-3) = 5, 第七天買入A股票，價格為1, 第九天賣出得價差為(10-1) = 9, 總利潤為各價差相加 = 4+5+9 = 18

解題想法 : 
首先定義遞迴函式solve()：
solve({stock.first, stock.second}, profit, day)
solve({股票買入價格,股票來源}, 當前利潤, 當前天數)
其中{}為一個pair, 使用上較方便, 並且定義{-1,'\0'}為目前手上沒有股票的情形。
(c++ pair 參考: https://www.796t.com/content/1548114125.html)

再來就是會遞迴到的呼叫形式：

假如今天是第day天且 :
1. 如果現在手上有股票
1-1. 現在持有A股票,而且今天要賣,那麼隔天的solve()則為
solve({-1,'\0'},profit+(A[day]-stock.first),day+1)
1-2. 現在持有B股票,而且今天要賣,那麼隔天的solve()則為
solve({-1,'\0'},profit+(B[day]-stock.first),day+1)
1-3. 跳過今天，甚麼也不做
solve({stock.first, stock.second}, profit, day+1)
最大利潤會是1-1, 1-2, 1-3三種狀況取最大值,回傳該值。

2. 如果現在手上沒股票
2-1. 買A股票,那麼隔天的solve()則為
solve({A[day],'A'}, profit, day+1)
2-2. 買B股票,那麼隔天的solve()則為
solve({B[day],'B'}, profit, day+1)
2-3. 跳過今天，甚麼也不做
solve({stock.first, stock.second}, profit, day+1)
最大利潤會是2-1, 2-2, 2-3三種狀況取最大值,回傳該值。

3. 例外(終止條件)
當今天已經是第m天的時候，則直接回傳profit(後面不能也不可能再賺錢)

根據上述定義，初始呼叫solve()應為
solve({-1,'\0'}, 0, 0) (手上沒股票, 利潤為0, 第0天)

//C++ language
//solution link(含註解): https://github.com/CBJ0519/CBJsProgramDiary.com/blob/main/%E8%B3%87%E8%A8%8A%E5%AD%B8%E7%A7%91%E8%83%BD%E5%8A%9B%E7%AB%B6%E8%B3%BD/111%E5%BD%B0%E9%9B%B2%E5%98%89/Q3-%E6%88%91%E6%98%AF%E8%82%A1%E7%A5%9E.cpp

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
int m;
vector<int>a,b;
int solve(pair<int,char> stock, int profit, int day){
    if(day == m){
        return profit;
    }
    if(stock.first != -1){
        if(stock.second == 'A')
            return max( solve({-1,'\0'}, profit+(a[day]-stock.first), day+1),
                        solve(stock, profit, day+1) );
        else{
            return max( solve({-1,'\0'}, profit+(b[day]-stock.first), day+1),
                        solve(stock, profit, day+1) );
        }
    }
    return max( solve({a[day],'A'}, profit, day+1),
                max(solve({b[day],'B'}, profit, day+1),
                    solve({-1,'\0'}, profit, day+1) ));
}
int main(){
    cin>>m;
    for(int i=0;i<m;i++){
        int x;cin>>x;
        a.push_back(x);
    }
    for(int i=0;i<m;i++){
        int x;cin>>x;
        b.push_back(x);
    }
    cout<<solve({-1,'\0'},0,0)<<"\n";
    return 0;
}