# APCS實作題2023年10月第4題：投資遊戲
> 日期：2024年8月16日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=m373)
## 題目
### 問題描述
你擁有一個長度為 $n$ 的陣列，代表每天的投資收益，以及 $k~(1 \leq k \leq 20)$ 張金牌。
你可以自行決定投資的開始和結束日期。在你選擇投資的每一天，你可以選擇消耗一張金牌來跳過當天，或者不使用金牌而拿取當天的收益。你的目標是找出如何投資，以實現最大的總收益。
請注意，你只能在投資期間進出一次。
<br />
### 輸入說明
第一行包含兩個整數：$n$ 和 $k$，以空格分隔。$n$ 表示天數，$k$ 表示金牌數。
第二行包含 $n$ 個整數，以空格分隔，代表每天的投資收益。這些整數按照天數的順序給出，數值範圍為 $-10000$ 到 $10000$。
子題分數：
- 20%：滿足 $k=0$，且 $1 \leq n \leq 2000$。
- 20%：滿足 $k=0$，且 $1 \leq n \leq 150000$。
- 60%：滿足 $1 \leq k \leq 20$，且 $1 \leq n \leq 150000$。
<br />
### 輸出格式
請輸出一個整數，代表達到的最大收益。
<br />
### 範例輸入1
```
9 0
3 1 -2 3 -2 3 -5 2 2
```
### 範例輸出1
```
6
```
### 範例輸入2
```
9 2
3 1 -2 3 -2 3 -5 2 2
```
### 範例輸出2
```
12
```
### 範例輸入3
```
9 4
3 1 -2 3 -2 3 -5 2 2
```
### 範例輸出3
```
14
```
### 範例輸入4
```
3 0
-1 -5 -3
```
### 範例輸出4
```
0
```
<br /><br />
## Python 程式碼
### 寫法1
解題想法，開一個 $(n+1) \times (k+1)$ 的二維串列 dp，其中 $dp[i][j]$ 代表第 $i$ 天、使用 $k$ 面金牌的最大收益。在 for 迴圈之中，要先處理使用金牌的狀況，如果在第 $i$ 天使用 $j$ 面金牌，則 $dp[i][j]$ 會是前一天（第 $i-1$ 天)、使用 $j-1$ 面金牌的值，因此第8行寫成
```python
if j > 0: dp[i][j] = dp[i-1][j-1]
```
但也有可能在第 $i$ 天不使用金牌，第 $i$ 天使用 $j$ 面金牌的損益，第 $i-1$ 天使用 $j$ 面金牌的損益加上當天的損益 $data[i]$，再與第8行處理過、使用金牌的損益比較取最大值，因此第9行寫成
```python
dp[i][j] = max(dp[i-1][j] + data[i], dp[i][j])
```
第9筆測資超時。
```python=
n, k = map(int, input().split()) # 讀取天數 n、金牌數量 k
data = [0] # 每天的損益資料，為了配合讀取時的索引值，先放入第0天的資料0
data += list(map(int, input().split())) # 讀取每天的損益資料
dp = [[0]*(k+1) for _ in range(n+1)] # dp[i][j] 為第i天、使用j面金牌的最大收益
for i in range(1, n+1): # i = 1 ~ n
for j in range(k+1): # j = 0 ~ k
if j > 0: dp[i][j] = dp[i-1][j-1] # 先處理使用金牌的狀況
dp[i][j] = max(dp[i-1][j] + data[i], dp[i][j]) # 第一項為不使用金牌的損益，取兩項中較大者
ans = 0 # 答案預設為 0
for d in dp: ans = max(ans, *d) # 依序由 dp 讀取資料 d，再用 * 拆開與 ans 一起取最大值
print(ans) # 印出答案
```
<br />
雖然把第12行放在前一個 for 迴圈之中，少跑一次 for 迴圈，但仍然會在第9筆測資超時。
```python=
n, k = map(int, input().split()) # 讀取天數 n、金牌數量 k
data = [0] # 每天的損益資料，為了配合讀取時的索引值，先放入第0天的資料0
data += list(map(int, input().split())) # 讀取每天的損益資料
dp = [[0]*(k+1) for _ in range(n+1)] # dp[i][j] 為第i天、使用j塊金牌的最大收益
ans = 0 # 答案預設為 0
for i in range(1, n+1): # i = 1 ~ n
for j in range(k+1): # j = 0 ~ k
if j > 0: dp[i][j] = dp[i-1][j-1] # 先處理使用金牌的狀況
dp[i][j] = max(dp[i-1][j] + data[i], dp[i][j]) # 第一項為不使用金牌的損益，取兩項中較大者
ans = max(ans, dp[i][-1]) # 因為 dp[i] 的最後一項是 dp[i] 的最大值，最取 ans 及 dp[i][-1] 之中較大者
print(ans) # 印出答案
```
<br /><br />
### 寫法2
吳邦一教授的寫法，利用滾動陣列節省時間及使用的記憶體。費時最久約為 1.6 s，使用記憶體最多約為 19.9 MB，通過測試。
```python=
n, k = map(int, input().split()) # 讀取天數 n、金牌數量 k
val = list(map(int, input().split())) # 讀取每天的損益資料
d = [0]*(k+1) # 前一天使用 j 面金牌的最大損益
p = [0]*(k+1) # 今天使用 j 面金牌的最大損益
ans = 0 # 答案預設為 0
for v in val: # 由 val 依序讀取當天的損益 v
p[0] = max(d[0], 0) + v # 先處理不用金牌的狀況，取前一天損益 d[0] 與 0 較大者，再加上 v
for j in range(1, k+1): # j = 1 ~ k
p[j] = max(d[j] + v, d[j-1]) # 第一項為不使用金牌、第二項為使用金牌的損益，取兩項中較大者
ans = max(ans, p[-1]) # 因為 p 的最後一項是 p 的最大值，最取 ans 及 p[-1] 之中較大者
d, p = p, d # 交換 d、p 的內容
print(ans) # 印出答案
```
<br /><br />
## C++ 程式碼
### 寫法1
費時最久約為 44 ms，使用記憶體最多約為 13.9 MB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, k; cin >> n >> k; // 讀取天數 n、金牌數量 k
vector<vector<int>> dp (n+1, vector<int> (k+1, 0)); // dp[i][j] 為第i天、使用j面金牌的最大收益
for(int i=1; i<=n; i++) { // i = 1 ~ n
int v; cin >> v; // 讀取第i天的損益
for(int j=0; j<=k; j++) { // j = 0 ~ k
if (j > 0) dp[i][j] = dp[i-1][j-1]; // 先處理使用金牌的狀況
dp[i][j] = max(dp[i-1][j] + v, dp[i][j]); // 第一項為不使用金牌的損益，取兩項中較大者
}
}
int ans = 0; // 答案預設為 0
for(auto d : dp) ans = max(ans, d.back()); // 取 ans 與 d.back() 之中的最大值
cout << ans << "\n"; // 印出答案
return 0;
}
```
<br />
如果將上方程式碼之中找 ans 的第18、19行移到前一個 for 迴圈之中，處理完 dp[i] 之後更新 ans，可以少跑一次 for 迴圈，花費的時間可以再少一點。費時最久約為 36 ms，使用記憶體最多約為 13.9 MB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, k; cin >> n >> k; // 讀取天數 n、金牌數量 k
vector<vector<int>> dp (n+1, vector<int> (k+1, 0)); // dp[i][j] 為第i天、使用j塊金牌的最大收益
int ans = 0; // 答案預設為 0
for(int i=1; i<=n; i++) { // i = 1 ~ n
int v; cin >> v; // 讀取第i天的損益
for(int j=0; j<=k; j++) { // j = 0 ~ k
if (j > 0) dp[i][j] = dp[i-1][j-1]; // 先處理使用金牌的狀況
dp[i][j] = max(dp[i-1][j] + v, dp[i][j]); // 第一項為不使用金牌的損益，取兩項中較大者
}
ans = max(ans, dp[i].back()); // 取 ans 與 dp[i].back() 之中的最大值
}
cout << ans << "\n"; // 印出答案
return 0;
}
```
<br /><br />
### 寫法2
吳邦一教授的寫法，利用滾動陣列節省時間及使用的記憶體。費時最久約為 35 ms，使用記憶體最多約為 348 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, k; cin >> n >> k; // 讀取天數 n、金牌數量 k
vector<int> d (k+1, 0), p (k+1, 0); // 前一天、今天使用 j 面金牌的最大收益
int ans = 0; // 答案預設為 0
for(int i=1; i<=n; i++) { // i = 1 ~ n
int v; cin >> v; // 讀取第i天的損益
p[0] = max(d[0], 0) + v; // 處理不使用金牌的狀況，取 d[0] 及 0 較大者再加上 v，取 0 代表放棄之前的損益
for(int j=1; j<=k; j++) { // j = 1 ~ k
p[j] = max(d[j] + v, d[j-1]); // 第一項為不使用金牌的損益，取兩項中較大者
}
ans = max(ans, p.back());
swap(d, p);
}
cout << ans << "\n"; // 印出答案
return 0;
}
```
<br /><br />
---
###### tags:`APCS`、`Python`、`C++`
Sign in with Wallet
Connect another wallet