# APCS 2023.10實作題題解C++與Python
在這份筆記中，我們說明APCS 2023年10月實作題考試的題目解說。這些題目是根據ZeroJudge上的版本，與真實考試的版本題意應該是一樣的，但題目敘述、測資與環境並不一定相同。
每一題的題解都包含題意分析、演算法、C/C++範例程式與Python範例程式。其中後兩個單元是獨立的，也就是必要的說明會在兩個單元重複出現，為了方便有些人只看其中一種語言。
## 第一題 機械鼠 (ZeroJudge m370)
### 題意分析
[(題目連結)1.機械鼠](https://zerojudge.tw/ShowProblem?problemid=m370)
數線上有一隻老鼠一開始位於位置$x$，有$n$個位置上有食物，老鼠只能往左邊或往右挑一個方向移動，經過食物時可以停下來吃食物，吃完後可以選擇繼續往相同方向移動，或者是結束今天的覓食。請問老鼠最多能吃到多少個食物，以及最後停下來吃食物的位置。
數線上有個起點$x$，另外有$n$個數字，比$x$大與比$x$小的個數哪個多，就是能吃到的食物數量，如果是$<x$，停下的位置就是最小值，否則是最大值。$n$保證是奇數且食物位置不會出現在$x$，也就是不會左右平手一樣多的狀況。
第一子題(二級分程度)是$n=3$，也就是不需要迴圈可做。
### 演算法構思與程式流程
首先，當然要讀入$x$與$n$，我們需要知道$<x$與$>x$的個數，可以歷遍這$n$個位置，並且用兩個變數$left$與$right$分別記錄。另外，我們還需要知道最後停下的位置，也就是位置的最大值與最小值，這個可以在歷遍的時候順便做，也可以等決定左右後另外再計算。第一題我們盡量減少庫存函數的使用，降低初學者的負擔。
### C/C++範例程式
宣告整數$left$與$rigth$來存左右食物數量，初值給0。以$lfin$來記錄左極值，也就是食物的最小值，初值給不可能的大(本題100)；另$rfin$來記錄右極值，也就是食物的最大值，初值給不可能的小(本題-100)。接著，一邊讀入食物位置$p$，一邊利用if判斷$p<x$或是$p>x$，同時維護好上述四個變數的定義(迴圈不變性)就行了。
最後依據題意輸出。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x,p,left=0, right=0, lfin=100, rfin=-100;
cin >> x >>n;
for (int i=0; i<n; i++) {
cin >> p;
if (p < x) {
left++;
if (p < lfin) lfin = p;
} else {
right++;
if (p > rfin) rfin = p;
}
}
if (left > right) {
cout << left <<' '<<lfin<<'\n';
} else { // (right>left)
cout << right <<' '<<rfin<<'\n';
}
return 0;
}
```
### Python範例程式
使用Python者需要對list與基本函數(例如max,min)有基本認識。第一第二行是輸入，用慣用的手法來輸入一行若干整數，這裡我們全把一行的輸入、分拆、與轉換整數後放在一個list，第一行直接unpack給$x$與$n$，第二行就放在$p$這個list中。
第3行給$left$與$right$的初值，這是要記錄左右食物數量的變數，接著歷遍$p$中的每個值，也就是食物位置，用if判斷是$right$或是$left$需要加一。
最後分兩種情況輸出，如果是$right>left$，我們要輸出$right$與$\max(p)$，否則輸出$left$與$\min(p)$。留意Python的print預設格式就是項目之間一個空白，剛好符合題目要求。
```python=
x,n = [int(t) for t in input().split()]
p = [int(t) for t in input().split()]
left = right = 0
for t in p:
if t>x: right += 1
else: left += 1
if right>left:
print(right,max(p))
else:
print(left,min(p))
```
## 第二題 卡牌遊戲 (ZeroJudge m371)
### 題意分析
[(題目連結) 2.卡牌遊戲](https://zerojudge.tw/ShowProblem?problemid=m371)
有一個$m\times n$的矩陣(Grid方格圖)，每個格子有一個卡牌，卡牌都是$[0,1000]$範圍內的整數，兩個相同數字的卡牌，如果在同列或同行且中間如果沒有其他的卡牌，就可以移除這兩張卡牌並得到卡牌上的分數。請問最大的得分。每一個出現的數字保證恰好出現兩張。
### 演算法構思與程式流程
每個出現的數字恰好現兩次。這件事的意思是說：若能移除不會有多種選擇，所以能移除就移除，這題就是個模擬題，只要模擬移除的動作就可以了。如果沒有恰出現兩次的限制，這個題目就困難了，有點類似以前有個電動遊戲四川省。
我們可以用一個不存在的數字來表示移除後的空白，例如-1。每一回合就針對每一個位置，都檢查它的右邊與下方，是否有可移除的對象。那要做到何時為止呢？這是個常用技巧，每一回合我們看看是否有牌被移除，若有，下回合就繼續；若整個矩陣掃完都沒有新的被移除的牌，就可以結束了。以下是虛擬碼流程。請留意我們只需要找下方與右方就足夠。
```
輸入資料
modify = True
while modify do
modify = False
for each position (r,c) do
if (r,c)是空 then
continue
end if
找下方第一個非空位置
if 相同 then
移除並更新答案
modify = True
end if
找右方第一個非空位置
if 相同 then
移除並更新答案
modify = True
end if
end for
end while
輸出答案
```
APCS的前兩題都不會有時間複雜度的問題(除非用了太扯的方法)，上述的做法時間複雜度如何呢？同一列每個位置找右方所需要的總時間不會超過$n$，同一行則是$m$，所以一回合只需要$O(mn)$，最多做$O(mn)$個回合，所以是$O(m^2 n^2)$，這題$m\leq 20, n\leq 40$，所以完全不會有問題。
### C/C++範例程式
我們宣告一個二維陣列來放矩陣，第6 ~ 11行是輸入。第12行的ans來記答案，modify來檢查是否要繼續。然後開始跑一個迴圈。
迴圈內歷遍所有矩陣位置，對於每一個位置，如果是-1就不必做。否則我們先找下方第一個非空位置，這個可以用第18行的for迴圈來找，然後檢查如果是相同的牌，就進行更新答案與移除的動作，所謂移除就是將該兩張牌改成-1。接著對右邊也做相同的處理。請留意，當進入while迴圈時，我們把modify改成0，有移除發生時，要把modify改成1，當歷遍結束時，根據modify就可以知道是否需要繼續。
變數的使用最好能有固定的習慣，筆者習慣用$r,c$分別代表列與行，再有變數就用$i$表示列，$j$表示行，這樣的程式寫法自己比較容易知道在做甚麼，也比較不容易犯錯。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, i,j,m,r,c;
int a[52][52]={0};
cin >> m>>n;
for (i=0;i<m;i++) {
for (j=0;j<n;j++) {
cin >> a[i][j];
}
}
int ans=0, modify=1;
while (modify) {
modify = 0;
for (r=0; r<m; r++) for (c=0; c<n; c++) {
if (a[r][c]<0) continue; // -1 for empty
// find first nonempty at downward
for (i=r+1; i<m && a[i][c]<0; i++);
if (i<m && a[i][c]==a[r][c]) {
ans += a[r][c];
a[i][c]=a[r][c]=-1; // clear
modify = 1; // need check futher
continue;
}
// find first non-empty at right side
for (j=c+1; j<n && a[r][j]<0; j++);
if (j<n && a[r][j]==a[r][c]) {
ans += a[r][c];
a[r][j]=a[r][c]=-1;
modify = 1;
}
}
}
// output
cout <<ans<<'\n';
return 0;
}
```
### Python範例程式
第1 ~ 6行是輸入，我們在矩陣的右方與下方加了一個不會出現的1001當做哨兵，這是用來省略邊界檢查的。
第7 ~ 8行的ans來記答案，modified來檢查是否要繼續。然後開始跑一個迴圈。
每次進入迴圈，都以雙迴圈歷遍所有矩陣位置(第11 ~ 12行)，對於每一個位置，如果是-1就不必做。否則我們先找下方第一個非空位置，這個可以用第15 ~ 16行的while迴圈來找，可以注意到這裡不需要邊界檢查。然後檢查如果是相同的牌，就進行更新答案與移除的動作，所謂移除就是將該兩張牌改成-1。接著對右邊也做相同的處理。請留意，當進入while迴圈時，我們把modified改成False，有移除發生時，要把modified改成True，當歷遍結束時，就可以知道是否需要繼續。
變數的使用最好能有固定的習慣，筆者習慣用$r,c$分別代表列與行，再有變數就用$i$表示列，$j$表示行，這樣的程式寫法自己比較容易知道在做甚麼，也比較不容易犯錯。
```python=
m,n = [int(t) for t in input().split()]
mat = []
# read matrix and add sentinel
for i in range(m):
mat.append([int(t) for t in input().split()]+[1001])
mat.append([1001]*n)
ans = 0
modified = True
while modified:
modified = False
for r in range(m):
for c in range(n):
if mat[r][c]<0: continue # -1 = empty
# find first non-empty downward
i = r+1
while mat[i][c]<0: i += 1
if mat[r][c] == mat[i][c]:
ans += mat[r][c]
mat[r][c]=mat[i][c]=-1
modified = True
continue
# check right side
j = c+1
while mat[r][j]<0: j += 1
if mat[r][c] == mat[r][j]:
ans += mat[r][c]
mat[r][c]=mat[r][j]=-1
modified = True
# end for
#end while
print(ans)
```
## 第三題 搬家 (ZeroJudge m372)
### 題意分析
[(題目連結) 3. 搬家](https://zerojudge.tw/ShowProblem?problemid=m372)
有一個$m\times n$的方格圖(矩陣)，每一格可能有水管或是沒有。每一種水管可能在上下左右的某幾個方向有接口，相鄰的兩格如果有接口相對接，則視為連通。找最大連通區塊。輸入以每一列一個字串表示，每一個字元代表該格子的水管種類。水管的開口方向與字元對應關係如下，基本上是象形文字
F: 右和下
H: 左和右
7: 左和下
I: 上和下
X: 上、下、左和右
L: 右和上
J: 左和上
0: 沒有水管
### 演算法構思與程式流程
既然是找連通區塊，這題就是DFS或BFS的graph traversal問題，BFS與DFS都是標準的演算法，步驟就不在此多說，不熟悉的讀者可以查閱課本或者網路。
本題稍微麻煩的是相鄰兩格是否連通的判斷，解題經驗豐富的話可以寫得比較漂亮，否則可能程式寫得非常長。如果枚舉$8\times 8=64$種組合，再配上4個方向，那就寫不出來了吧。以下我們說明比較好的判斷方式。
除了'0'是沒有水管，我們可以把水管歸類，對於東南西北4個方位，給每個方位有接口的水管種類列出來，這樣處理一個格子時，我們可以很容易決定某個方位是否有接口。至於歸類檢查的方法有多種，以下範例程式中我們列出多種以供參考。
這裡將示範BFS的寫法，DFS的方法可以適用在C/C++，但Python可能會有記憶體的問題，事實上，筆者在ZeroJudge測試本題時，C++也有一筆測資DFS會記憶體不夠。
### C/C++範例程式
第一個範例我們用C++來寫，至於接口檢查歸類的方法，我們把東南西北是否有接口寫成4個簡單的函數(第5 ~ 16行)。
主程式一開始先讀入輸入資料，然後跑一個雙迴圈歷遍每一個位置，visited是宣告在全域的變數，用以表示一個點是否已經走過，走過就不應該再走。歷遍時，如果發現有水管且沒有走過，我們就開始一個BFS，計算連通區塊的大小並且將走過的點設定visited為1。
要啟動BFS，我們用一個vector當做queue，裡面存的是列與行的pair，另外也可以用陣列來做，可以參考下一個範例程式的寫法。這裡我們不將離開que的元素刪除，只用一個變數紀錄頭端位置。初始將本次起點放入que中，並標示為visited，跑一個while迴圈，每次頭端取出一個位置，檢查4方位鄰居，如果沒有出界且沒有走過且我在那個方向有接口且對方在相反方向有接口，則將對方納入que中並標示為visited。
這樣while迴圈跑完que的大小就是本次走訪連通區塊的大小，我們要在各次走訪的區塊中取最大值，最後輸出。
```cpp=
#include<bits/stdc++.h>
using namespace std;
int visited[510][510]={0};
bool east(char ch) {
return ch=='H' || ch=='L' || ch=='F' || ch=='X';
}
bool west(char ch) {
return ch=='H' || ch=='J' || ch=='7' || ch=='X';
}
bool south(char ch) {
return ch=='I' || ch=='7' || ch=='F' || ch=='X';
}
bool north(char ch) {
return ch=='I' || ch=='L' || ch=='J' || ch=='X';
}
int main() {
int m,n,i,j;
string mat[510];
cin>>m>>n;
for (i=0;i<m;i++) cin >> mat[i];
int imax=0, t;
for (i=0;i<m;i++) for (j=0;j<n;j++) {
if (mat[i][j]=='0' || visited[i][j]) continue;
// bfs
vector<pair<int,int>> que;
int head=0;
que.push_back({i,j});
visited[i][j] = 1;
while (head < que.size()) {
int r=que[head].first, c=que[head].second;
head++;
// check 4 neighbor
if (c<n-1 && !visited[r][c+1] && east(mat[r][c]) && west(mat[r][c+1])) {
que.push_back({r,c+1});
visited[r][c+1] = 1;
}
if (c>0 && !visited[r][c-1] && west(mat[r][c]) && east(mat[r][c-1])) {
que.push_back({r,c-1});
visited[r][c-1] = 1;
}
if (r<m-1 && !visited[r+1][c] && south(mat[r][c]) && north(mat[r+1][c])) {
que.push_back({r+1,c});
visited[r+1][c] = 1;
}
if (r>0 && !visited[r-1][c] && north(mat[r][c]) && south(mat[r-1][c])) {
que.push_back({r-1,c});
visited[r-1][c] = 1;
}
}
imax = max(imax,(int)que.size()); // component size
}
printf("%d\n", imax);
return 0;
}
```
以下我們再示範一個C的寫法，這裡的歸類檢查接口也改採另外一個方法，供大家參考。
我們將每一個方向有接口的水管字元放在一個字串中，搭配慣用的4方位給予0 ~ 3來表示，我們可以列出第6行中的4個字串陣列，此處因為後面需要找相反方向，所以0 ~ 3不要亂給，順時針或逆時針給定，那麼相對方向可以很容易決定。第5行的visited與第8行的que_r, que_c, head, tail都是BFS要用的變數，這裡我們把一個點的列與行分別存在兩個陣列中。輸入與BFS的架構與前一個範例程式是類似的，就不多做解釋，差別在第24行檢查接口的地方。我們跑一個迴圈檢查4個鄰居，用strchr這個字串函數檢查字元是否在字串中，也就是這一個在這個方位是否有接口，對面的格子也是類似，但方位是$(d+2)\%4$。
```c=
#include <stdio.h>
#include <string.h>
char mat[510][510];
int visited[510][510]={0};
char dstr[4][10] = {"HLFX","I7FX","HJ7X","ILJX"}; // East,South,West,North
int dr[4]={0,1,0,-1}, dc[4]={1,0,-1,0};
int que_r[250000],que_c[250000],head,tail; // que row and col
int main() {
int m,n,i,j;
scanf("%d%d",&m,&n);
for (i=0;i<m;i++) scanf("%s",mat[i]);
int imax=0, t;
for (i=0;i<m;i++) for (j=0;j<n;j++) {
if (mat[i][j]=='0' || visited[i][j]) continue;
// bfs
que_r[0] = i; que_c[0] = j;
head = 0; tail = 1; // que [head,tail)
visited[i][j] = 1;
while (head < tail) {
int r=que_r[head], c=que_c[head];
head++;
for (int d=0; d<4; d++) {
int nr=r+dr[d],nc=c+dc[d];
if (nr<0 || nr>=m || nc<0 || nc>=n || visited[nr][nc])
continue;
if (strchr(dstr[d],mat[r][c])!=NULL && \
strchr(dstr[(d+2)%4],mat[nr][nc])!=NULL) {
que_r[tail] = nr; que_c[tail] = nc;
tail++;
visited[nr][nc] = 1;
}
}
}
if (tail > imax) imax = tail; // component size
}
printf("%d\n", imax);
return 0;
}
```
### Python範例程式
以下介紹Python的BFS解法。我們把BFS寫成一個函數，走過的位置改成'0'來表示，省略了visited的檢查。第一件要留意的事是Python的字串是immutable，所以讀入後我們把它的字元拆開來放入list中(第25行)。
這裡BFS所需的queue用list加上一個頭端位置的變數head來做，這是筆者比較推薦的方法，切不可在用que.pop(0)的方式移除頭端，那樣做時間複雜度是糟糕的。我們將點放入que中時，把該位置的字元一併放入，如此，我們可以把該位置改成'0'而省略另外用list來檢查是否走過。
Python的程式要決定某個字元是否在某個字串中很好寫，我們將每一個方向有接口的水管字元放在一個字串中，如此很容易檢查相鄰兩格在相對位置是否都有接口，4個方向我們用4個if來做(第7 ~ 18行)。最後，走訪過的數量就是que的長度。
主程式很簡單，輸入後，跑雙迴圈歷遍每一個點，如果不是'0'就走一個BFS，回傳的大小與最大值。
```python=
#dstr = ["HFLX","F7IX","H7JX","LIJX"]
def bfs(r,c,mat,m,n):
que = [(r,c,mat[r][c])]; head = 0
mat[r][c] = '0'
while head < len(que):
r,c,me = que[head]; head += 1
if c<n-1 and me in "HFLX" and mat[r][c+1] in "H7JX":
que.append((r,c+1,mat[r][c+1]))
mat[r][c+1] = '0'
if c>0 and me in "H7JX" and mat[r][c-1] in "HFLX":
que.append((r,c-1,mat[r][c-1]))
mat[r][c-1] = '0'
if r<m-1 and me in "F7IX" and mat[r+1][c] in "LIJX":
que.append((r+1,c,mat[r+1][c]))
mat[r+1][c] = '0'
if r>0 and me in "LIJX" and mat[r-1][c] in "F7IX":
que.append((r-1,c,mat[r-1][c]))
mat[r-1][c] = '0'
return len(que)
m,n = [int(t) for t in input().split()]
mat = []
for i in range(m):
mat.append(list(input()))
#print(mat)
imax = 0
for i in range(m):
for j in range(n):
if mat[i][j]=='0': continue
imax = max(imax,bfs(i,j,mat,m,n))
#
print(imax)
```
我們再給另外一種寫法去檢查相鄰格子是否有接口，這個寫法運用格子點慣用的4方位寫法，在第1行先定義了東南西北四方位的列與行移動量。此外，水管在四個方位可能有接口，我們可以用4個bit以二進位的方式將每一個水管編碼成0 ~ 15的整數：在方向$i$有接口則第$i$個bit是1，編碼的結果放在字典中(第15行)，殊入字串時，直接轉換成新編碼放入(第18行)。
在決定是否相通時，跑一個0 ~ 3的迴圈(第7行)用bit決定我的第$i$個bit是否為1，而對方在$(i+2)\%4$的bit是否是1，請留意$(i+2)\%4$就是$i$的相反方向。此外，這裡我們沒有檢查邊界，因為輸入時在最右邊與最下邊加了0的哨兵。
註：有些Python在Grid中走訪的小技巧可以參考筆者了另外一篇筆記 [Python-LeetCode 581 第三招 Grid Traversal ](/KNjxtbQPQ9GoObErkZAoKQ)
```python=
dr,dc = [0,1,0,-1],[1,0,-1,0] # East,south,west,north
def bfs(mat,r,c):
que = [(r,c,mat[r][c])]; head = 0
mat[r][c] = 0
while head < len(que):
r,c,me = que[head]; head += 1
for i in range(4):
nr,nc = r+dr[i],c+dc[i]
if (me&(1<<i)) and (mat[nr][nc]&(1<<((i+2)%4))):
que.append((nr,nc,mat[nr][nc]))
mat[nr][nc] = 0
return len(que)
m,n = [int(t) for t in input().split()]
d = {'H':5,'F':3,'L':9,'I':10,'7':6,'J':12,'X':15,'0':0}
mat = []
for i in range(m):
mat.append([d[c] for c in input()]+[0])
mat.append([0]*(n+1))
#print(mat)
imax = 0
for i in range(m):
for j in range(n):
if mat[i][j]:
imax = max(imax,bfs(mat,i,j))
#
print(imax)
```
## 第四題 投資遊戲 (ZeroJudge m373)
### 題意分析
[(題目連結) 4.投資遊戲](https://zerojudge.tw/ShowProblem?problemid=m373)
有一個長度為$n$的陣列，代表每天的投資收益，以及$k$張金牌，$k\leq 20$。只能在投資期間進出一次，你可以自行決定投資的開始和結束日期。在你選擇投資期間的每一天，你可以選擇消耗一張金牌來跳過當天，或者不使用金牌而拿取當天的收益(可能是負值)。你的目標是找出如何投資，以實現最大的總收益。
### 演算法構思與程式流程
當$k=0$時就是選取一個總和最大的區間，這是經典的Max Subarray問題。當$k>0$時，有人可能誤以為找出max subarray之後去除其中最小的$k$個負數就是答案，這是假解。
我們可能有很多個獨立的總和為正的區間，中間被很大的負值區隔開，金牌的存在讓我們可以將兩個獨立區間都納入。例如$[5,-10,7,-6,4,5,-3,2]$，這個輸入在$k=0$時答案是$[7,-6,4,5]$；$k=1$時，選相同的區間，消除內部的-6；$k=2$時，選$[5,-10,7,-6,4,5]$消除-10與-6是最佳解。
先回顧max subarray的解法。它有一個分治與一個DP的方法，分治那個通常拿來教學，因為DP解法太乾淨俐落了。
### DP for $k=0$ (max subarray)
假設陣列是$v$。令$d[i]$是以$i$結尾的最大區間總和值，考慮$d[i]$與$d[i-1]$的關係。$i$結尾的最大區間，可分兩種：
1. 不含$v[i-1]$。也就是只有$v[i]$一個元素，$d[i]=v[i]$。
2. 含$v[i-1]$。既然$d[i-1]$是$i-1$結尾的最大值，那麼從$i-1$往前的最大總和就是$d[i-1]$，所以此情形下$d[i]=d[i-1]+v[i]$。
兩種情形挑大的就是答案
$$
\begin{array}{lll}
d[i]&=&\max\{v[i],d[i-1]+v[i]\} \\
&=& \max\{d[i-1],0\} + v[i]
\end{array}
$$
最後答案是所有可能結尾中取最大值。
### DP for $k>0$
DP最重要的就是找出遞迴式。對於$k>0$，延續之前的想法，很自然的考慮以$i$結尾的子問題(狀態)，這時有金牌，所以我們把已使用的金牌數也當作參數，令$dp[j][i]$是以$i$結尾且金牌使用數不超過$j$的最大值。最後的解答在$\max_{0\leq r<n}dp[k][r]$。這裡我們定義為**不超過**$j$個是為了避免麻煩，因為有可能不到$k$個負值，那麼表格有些地方是沒定義，最大值發生位置也可能不在$[k]$。
遞迴式很簡單，$j=0$時，與max subarray一樣
$$
dp[0][i] = \max\{dp[0][i-1],0\}+v[i]
$$
當$j>0$時，第$i$天可以用金牌也可以不用金牌。若不使用金牌，$dp[j][i] = dp[j][i-1]+v[i]$；若使用金牌，$dp[j][i] = dp[j-1][i-1]$。兩者取較大的
$$
dp[j][i] = \max\{dp[j][i-1]+v[i],dp[j-1][i-1]\}
$$
前置狀態在左邊與左上方，所以逐列逐行計算就可以了。
### C/C++範例程式
DP往往是方法難找而程式很簡單，本題也不例外。先揭示一個C的二維陣列的程範例式。程式就照著遞迴式，逐列逐行計算。
```c=
// dp[k,n] max subarray end at n and with at most k masked
// dp[0,n] = max(dp[0,n-1],0) + v[i]
// dp[k,n] = max(dp[k-1,n-1], dp[k,n-1]+v[i]) for k>0
// using 2d array
#include <stdio.h>
#define N 150010
#define K 22
int v[N],dp[K][N];
int main() {
int n, i,j,m,t,k;
scanf("%d%d",&n,&k);
for (i=0;i<n;i++) scanf("%d",&v[i]);
dp[0][0] = v[0];
for (i=1; i<n; i++) {
dp[0][i] = v[i];
if (dp[0][i-1]>0) dp[0][i] += dp[0][i-1];
}
for (j=1; j<=k; j++) {
dp[j][0] = (v[0]>0)? v[0]: 0;
for (i=1; i<n; i++) {
dp[j][i] = (dp[j][i-1]+v[i] > dp[j-1][i-1])? \
dp[j][i-1]+v[i]: dp[j-1][i-1];
}
}
int imax = 0;
for (i=0; i<n; i++)
if (dp[k][i]>imax) imax = dp[k][i];
printf("%d\n",imax);
return 0;
}
```
以下我們揭示一個C++的範例程式，這麼簡單的程式根語言的關係都不大，但這題有個常用節省空間的方法，我們介紹一下。因為每一行只跟前一行有關，所以我們可以用兩個一維陣列，一個叫$d$一個叫$p$，來替代二維陣列。我們每次都從$d$算到$p$，然後在迴圈結尾交換兩陣列，這個方法稱為滾動陣列。物件的交換只要$O(1)$，這比複製要省一點時間。這裡我們用vector來做。
```cpp=
// dp[k,n] max subarray end at n and with at most k masked
// dp[0,n] = max(dp[0,n-1],0) + v[i]
// dp[k,n] = max(dp[k-1,n-1], dp[k,n-1]+v[i]) for k>0
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, i,j,m,t,k;
cin >> n>>k;
vector<int> v(n,0);
for (i=0;i<n;i++) cin>>v[i];
vector<int> d(k+1,0),p(k+1,0); // from d to p
int imax = 0;
for (int i=0;i<n;i++) {
p[0] = max(d[0],0)+v[i];
for (int j=1; j<=k; j++) {
p[j] = max(d[j-1],d[j]+v[i]);
}
d.swap(p);
imax = max(imax,d[k]);
}
cout << imax<<'\n';
return 0;
}
```
### Python範例程式
DP往往是方法難找而程式很簡單，而且跟使用哪一種語言關係不大，本題也不例外。使用Python與C++差不多。
這題有個常用節省空間的方法，我們介紹一下。因為每一行只跟前一行有關，所以我們可以用兩個一維陣列，一個叫$d$一個叫$p$，來替代二維陣列。我們每次都從$d$算到$p$，然後在迴圈結尾交換兩陣列，這個方法稱為滾動陣列。物件的交換只要$O(1)$，這比複製要省一點時間。
```python=
n,k = [int(x) for x in input().split()]
val = [int(x) for x in input().split()]
d,p = [0]*(k+1),[0]*(k+1)
imax = 0
for v in val:
p[0] = max(d[0],0) + v
for j in range(1,k+1):
p[j] = max(d[j-1], d[j]+v)
d,p = p,d
imax = max(imax,d[k])
print(imax)
```
Sign in with Wallet
Connect another wallet