# APCS 2024.01實作題題解 --- C++與Python

在這份筆記中，我們說明APCS 2024年1月實作題考試的題目解說。這些題目是根據ZeroJudge上的版本，與真實考試的版本題意應該是一樣的，但題目敘述、測資與環境並不一定相同。

每一題的題解都包含題意分析、演算法、C/C++範例程式與Python範例程式。其中後兩個單元是獨立的，也就是必要的說明會在兩個單元重複出現，為了方便有些人只看其中一種語言。

## 第一題 遊戲選角 (ZeroJudge m931)

### 題意分析

[(題目連結)1.遊戲選角](https://zerojudge.tw/ShowProblem?problemid=m931)
有 $n$ 個角色，每個角色有攻擊力和防禦力。角色的能力值是攻擊力和防禦力的平方和，輸出能力值第二大的攻擊力和防禦力數值。
保證每個角色的能力值相異。

把兩種能力看成XY座標，本題相當於輸入在平面上的 $n$ 個點座標，要找出距離原點第二遠的點。
第一子題(二級分程度)是$n=3$，也就是不需要迴圈可做。

### 演算法構思與程式流程

無論如何更改比較的方式，這題就是找第二大。找第二大與找最大是類似的方法。
我們歷遍全部的點，用pmax1,pmax2記錄著目前所看到的最大與第二大，當新的點進來時，有以下三種情形：
* 如果新的點大於pmax1：新的點成為最大，pmax1降為第二大，pmax2就不要了；
* 如果新的點小於pmax1但大於pmax2：新的點成為第二大(pmax2)；
* 如果新的點小於pmax2：不必理會。

我們維護好pmax1與pmax2的迴圈不變性，也就是它們是目前看到的最大與第二大，當歷遍結束後，pmax2就是答案。

### C/C++範例程式

本題要比的對象有兩個參數，比較的方式是兩個參數的平方和。我們用$(x1,y1)$表示目前的最大點，$pmax1$是它的平方和；類似的，以$(x2,y2)$表示目前的第二大點，$pmax2$是它的平方和。
初值給予不可能的小的-1，這樣寫比較方便，否則在進入迴圈前就要去比較前兩個點。接著跑一個$n$次的迴圈，每次讀取一個點$(x,y)$，然後根據前述流程更新最大點與第二大點就可以了。

// Q1, find second farthest point
// keep the max and second max while iterating
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, x,y, pmax1=-1, pmax2=-1,x1,y1,x2,y2;
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> x >> y;
        int p=x*x+y*y;
        if (p > pmax1) {
            pmax2 = pmax1;
            pmax1 = p;
            x2 = x1; y2 = y1;
            x1 = x; y1 = y;
        } else if (p > pmax2) {
            pmax2 = p;
            x2 = x; y2 = y;
        }
    }
    cout << x2 <<' '<<y2<<'\n';
    return 0;
}

### Python範例程式

使用Python者需要對list有基本認識以方便處理輸入。本題要比的對象有兩個參數，比較的方式是兩個參數的平方和。我們用$(x1,y1)$表示目前的最大點，$pmax1$是它的平方和；類似的，以$(x2,y2)$表示目前的第二大點，$pmax2$是它的平方和。

第3 ~ 4行是給予pmax1與pmax2不可能的小當初始值，本題平方和必然為非負。這樣寫比較方便，否則在進入迴圈前就要去比較前兩個點。
接著跑一個$n$次的迴圈，每次讀取一個點$(x,y)$，一行讀取兩個數字有多種方法，第6行的寫法是個輸入一行若干整數的慣用手法，這裡我們把一行的輸入、分拆、與轉換整數後放在一個list，然後直接unpack給$x$與$y$。
資料讀入後，根據前述流程更新最大點與第二大點就可以了。

# keep max and second max
n = int(input())
pmax1,x1,y1 = -1,-1,-1
pmax2,x2,y2 = -1,-1,-1
for i in range(n):
    x,y = [int(x) for x in input().split()]
    p = x*x+y*y
    if p > pmax1: # new max
        pmax2,x2,y2 = pmax1,x1,y1
        pmax1,x1,y1 = p,x,y
    elif p > pmax2: # new second max
        pmax2,x2,y2 = p,x,y
#
print(x2,y2)

找第二大也可以用sorting來做，雖然是有點殺雞用牛刀，但因為Python用這個寫法通常更簡潔，所以，如果會用sorting，這也是個好方法，以下是範例程式。
本題要比的是平方和，所以呼叫sort時要給key參數，並寫一個lambda function。

# using sorting to find second largest
n = int(input())
p = []
for i in range(n):
    p.append([int(x) for x in input().split()])
p.sort(key=lambda x: x[0]**2+x[1]**2)
print(*p[-2])

如果還不太會使用sort的key參數，另外一個替代的方式是將要比較的對象放在資料的第一個欄位，如以下的範例程式，注意我們在第5行讀入資料時，第6行是我們存入list中的值。

# using sorting to find second largest
n = int(input())
p = []
for i in range(n):
    x,y = [int(x) for x in input().split()]
    p.append((x*x+y*y, x, y))
p.sort()
print(p[-2][1], p[-2][2])

## 第二題 蜜蜂觀察 (ZeroJudge m932)

### 題意分析

[(題目連結) 2.蜜蜂觀察](https://zerojudge.tw/ShowProblem?problemid=m932)
模擬在一個$m\times n$的蜂巢中行走，每個格子有一個字母(如下圖右)，每個格子是六角形，方向的定義如下圖左(此圖取自ZeroJudge)。起點在左下角，給予每一步的方向，請模擬紀錄所走到格子的字母，以及經過字元的種類數（大小寫相異），若經過時碰到牆壁該行動會停在原地。

### 演算法構思與程式流程

這就是個模擬的題目，我們以矩陣的橫列與直行來定義位置，以變數$(r,c)$ 紀錄目前位置，每次先計算出下一步的位置，如果沒有出界，則將位置移到新的位置，否則(出界)的話，位置不改變。主要流程可以規劃如下：

初始 (r,c) = (m-1,0)
for each 下一步的方向 di do
    計算出 (r,c) 走方向 di 所到位置 (nr,nc)
    if (nr,nc) 沒有出界 then 
        (r,c) = (nr,nc)
    else
        (r,c) 不改變
    end if
    紀錄字母
end for
計算字母種類

要如何計算下一步的位置呢？最直接的方法是枚舉6個方向，也就是寫6個if。不過那樣寫會有點囉嗦，有個常用在格子點移動的小技巧可以讓這件事變得簡潔一些：
> 我們先將6個方向的列移動量與行移動量放在dr[]與dc[]陣列，那麼向方向d移動後的位置就是
> nr = r+dr[d]; nc = c + dc[d]

以本題6邊形的方向來說
dr = (-1,0,1,1,0,-1)
dc = (0,1,1,0,-1,-1)
舉例來說，方向0時，dr[0] = -1, dc[0] = 0 即表示列編號減一(往上)，而行編號不變。

最後一個問題是要找出所經過的字母中有多少相異的字母。
APCS的前兩題都不會有時間複雜度的問題(除非用了太扯的方法)，這題的路徑長度不超過100，所以用窮舉比對也可以，不過因為字母的個數很有限，用表格記錄那些出現的方式是比較好的。字母的ASCII都不超過127，我們可以用一個長度128的表格，將經過字母的ASCII的位置紀錄為1，沒有出現的為0，最後把表格內容加總一下就知道有多少相異字母。

### C/C++範例程式

因為C\++與C的字串處理方式很不一樣，我們先看C\++的寫法。
第5 ~ 16行是輸入。第17行開始模擬，依照前述的流程，將走過的字母記path字串中。第29行開始是計算相異字母。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int m,n,k,r,c;
    vector<string> board;
    // input
    cin >> m>>n>>k;
    for (int i=0; i<m; i++) {
        string row;
        cin >> row;
        board.push_back(row);
    }
    vector<int> imove(k);
    for (int i=0;i<k;i++) {
        cin>>imove[i];
    }
    r = m-1, c = 0; // initial position
    int dr[6]={-1,0,1,1,0,-1}, dc[6]={0,1,1,0,-1,-1}, nr,nc;
    string path;
    for (int d:imove) {
        nr = r+dr[d]; nc = c+dc[d];
        if (nr>=0 && nr<m && nc>=0 && nc<n) {
            r = nr; c = nc;
        }
        path += board[r][c];
    }
    cout << path<<'\n';
    // compute number of distinct char
    int cnt[128]={0}; // if appeared
    for (char c:path) cnt[c] = 1;
    int num = 0;
    for (int i=0; i<128; i++) num += cnt[i];
    cout << num<<'\n';
    return 0;
}

接著提供C的寫法。流程與方法皆相同，輸入與字串的處理方式則不相同。

#include <stdio.h>
#include <stdlib.h>
int main() {
    int m,n,k,r,c;
    char board[21][21],path[101];
    scanf("%d%d%d", &m, &n, &k);
    for (int i=0; i<m; i++) {
        scanf("%s",board[i]);
    }
    r = m-1, c = 0; // initial position
    int dr[6]={-1,0,1,1,0,-1}, dc[6]={0,1,1,0,-1,-1},nr,nc,d;
    for (int i=0;i<k;i++) {
        scanf("%d", &d);
        nr = r+dr[d]; nc = c+dc[d];
        if (nr>=0 && nr<m && nc>=0 && nc<n) {
            r = nr; c = nc;
        }
        path[i] = board[r][c];
    }
    path[k]='\0';
    // compute number of distinct char
    int cnt[128]={0}; // if appeared
    for (int i=0; i<k; i++) cnt[path[i]] = 1;
    int num = 0;
    for (int i=0; i<128; i++) num += cnt[i];
    printf("%s\n%d\n",path,num);
    return 0;
}

### Python範例程式

第1 ~ 9行是輸入與設初值，第10 ~ 15行是依照前述流程進行模擬，並且用字串path來記答案，第17 ~ 20行是計算不同字母數量，這裡用到ord(ch)是ch的ASCII code。如果會使用set，計算相異字母個數可以簡單的以第21行的方式計算出來。

m,n,k = [int(x) for x in input().split()]
p = []
for i in range(m):
    p.append(input())
move = [int(x) for x in input().split()]
path = "" # 
dr = (-1,0,1,1,0,-1)
dc = (0,1,1,0,-1,-1)
r,c = m-1,0
for d in move:
    nr,nc = r+dr[d],c+dc[d]
    if 0<=nr<m and 0<=nc<n:
        r,c = nr,nc
    path += p[r][c]
print(path)
# compute distinct char in path
cnt = [0]*128
for ch in path:
    cnt[ord(ch)] = 1
num = sum(cnt)
# num = len(set(path)) # using set
print(num)

## 第三題 邏輯電路 (ZeroJudge m933)

### 題意分析

[(題目連結) 3. 邏輯電路](https://zerojudge.tw/ShowProblem?problemid=m933)
本題題序較為複雜，詳細題目可以先看一下題目連結。大意是有一個如下圖的邏輯電路(此圖取自ZeroJudge)，包含輸入閘，輸出閘，以及若干邏輯閘，邏輯閘的種類包含AND, OR, XOR, NOT四種。根據輸入閘的輸入，請模擬計算出輸出閘的信號，此外，要計算**最大延遲**，定義為輸入閘到輸出閘最多經過幾個邏輯閘。此線路不會出現環路且最大延遲不超過100。


### 演算法構思與程式流程

不會形成迴路，所以這個圖就是個DAG (directed acyclic graph)，只要找出topological sort，然後依此順序計算每個閘輸出的信號(運算的結果)就可以了。至於最大延遲也就是DAG上的最長路徑問題，沿著此順序做簡單的DP就可以。以下是主要流程：
1. 找出一個topological sort。
2. 輸入閘的延遲初設為0。依照topological sort的順序，計算每一個節點的延遲時間為其前置節點中延遲的最大值加一。
3. 依照此順序，對於每一個邏輯閘與輸出閘，根據邏輯閘種類計算該閘的輸出信號。

計算一個topological sort是一個常用的標準程序，這裡就不再說明，有需要的讀者可以參考網路或者AP325中的演算法說明。

本題測資保證延遲不超過100，所以也可以用逆向的方式來做top-down DP，而Python 遞迴不至於過深。把一個輸出閘當作一棵樹的root，這個圖也可以看成很多樹交雜在一起(共用一些節點)，要求此輸出閘的結果，可以看成是樹的DP。以下我們會介紹這兩種寫法。

### C/C++範例程式

第一個範例我們用C++來寫順向的作法。這裡用到的資料比較多，說明如下，對於每個節點：
* data： 是該節點輸出端的信號
* gate： 是該節點的閘型態，1 ~ 4分別代表AND/OR/XOR/NOT，保留0給輸出閘
* d： 該節點的最大延遲
* pred：該節點的前置節點(predecessor)
* succ：該節點的後繼節點(successor)
* indeg：in-degree，也就是pred的大小

第21行之前是讀入輸入資料並設定上述的相關資料。第23 ~ 32是計算一個topological sort並儲存在seq中。它的前$p$個都是輸入閘。第36 ~ 54行是根據seq來計算每一個閘的最大延遲以及信號結果，其中NOT閘與輸出閘都只有一個前置節點，其他則是兩個前置節點。輸出閘的延遲我們不加1，因為延遲的定義是到達輸出閘的邏輯閘個數。最後是依照題目要求輸出最大延遲與模擬的結果。
程式有點長，因為用到的資料比較多且四種邏輯閘分開寫。時間複雜度是點數與邊數的線性時間，因為本題每個節點的in-degree最大是2，所以邊數在點數兩倍之內。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int p,q,r,m,i,j,u,v,n;
    scanf("%d%d%d%d",&p,&q,&r,&m); // in,gate,out,edge
    n = p+q+r; // total node
    vector<int> data(n+1),gate(n+1,0),d(n+1,0);
    for (i=1;i<=p;i++) {
        scanf("%d",&data[i]); // input signal
    }
    for (i=p+1;i<p+q+1;i++) {
        scanf("%d",&gate[i]); // gate type
    }
    vector<int> indeg(n+1,0);
    vector<vector<int>> succ(n+1), pred(n+1); // out and in neighbor
    for (i=0;i<m;i++) {
        scanf("%d%d",&u,&v);
        indeg[v]++;
        succ[u].push_back(v);
        pred[v].push_back(u);
    }
    // dag topological sort
    vector<int> seq;
    for (int i=1;i<=p;i++) seq.push_back(i);
    int head=0;
    while (head < seq.size()) {
        v = seq[head]; head++;
        for (int u: succ[v]) {
            indeg[u]--;
            if (indeg[u]==0) seq.push_back(u);
        }
    }
    // que is topological sort
    assert(seq.size()==n);
    // find max delay and result
    for (i=p; i<n; i++) { // ignore <p (input)
        int g = seq[i];
        if (gate[g]==1) {
            data[g] = data[pred[g][0]] & data[pred[g][1]];
            d[g] = max(d[pred[g][0]], d[pred[g][1]])+1; //delay
        } else if (gate[g]==2) {
            data[g] = data[pred[g][0]] | data[pred[g][1]];
            d[g] = max(d[pred[g][0]], d[pred[g][1]])+1;
        } else if (gate[g]==3) {
            data[g] = data[pred[g][0]] ^ data[pred[g][1]];
            d[g] = max(d[pred[g][0]], d[pred[g][1]])+1;
        } else if (gate[g]==4) { // NOT
            data[g] = 1-data[pred[g][0]];
            d[g] = d[pred[g][0]]+1;
        } else { // output
            data[g] = data[pred[g][0]];
            d[g] = d[pred[g][0]];
        }
    }
    int maxd=0;
    for (i=p+q+1; i<=n;i++) maxd = max(maxd,d[i]);
    printf("%d\n",maxd);
    for (i=p+q+1; i<n; i++) printf("%d ",data[i]);
    printf("%d\n",data[n]);
    return 0;
}

以下我們再示範一個用C的逆向寫法，也就是top-down DP的做法。
其實兩種方法的道理是一樣的，top-down寫遞迴的好處是不需要先找topological sort，所以也不需要記successor與in-degree，可以省一點事，這裡我們用$data[v]<0$來表示該點還沒有計算過。此外，前置點這裡稱為left-child與right-child。

// q3 topdown
#include <stdio.h>
#define N 60000
int dep[N]={0},data[N],gate[N],lc[N]={0},rc[N]={0};

void dp(int v) { // find data[v] and dep[v]
    if (data[v]>=0) return; // done
    dp(lc[v]); // left child
    if (gate[v]==4) { // NOT gate
        dep[v] = dep[lc[v]]+1;
        data[v] = 1-data[lc[v]];
        return;
    }
    dp(rc[v]); // right child
    // find depth
    dep[v] = (dep[lc[v]]>dep[rc[v]])? dep[lc[v]]+1:dep[rc[v]]+1;
    if (gate[v]==1) // AND
        data[v] = data[lc[v]] & data[rc[v]];
    else if (gate[v]==2) // OR
        data[v] = data[lc[v]] | data[rc[v]];
    else if (gate[v]==3) // XOR
        data[v] = data[lc[v]] ^ data[rc[v]];
    else ; // never happen
    return;
}

int main() {
    int p,q,r,m,i,j,u,v,n;
    scanf("%d%d%d%d",&p,&q,&r,&m); // in,gate,out,edge
    n = p+q+r; // total node
    for (i=0;i<=n;i++) data[i]=-1; // uncomputed
    for (i=1;i<=p;i++) scanf("%d",&data[i]); // input signal
    for (i=p+1;i<p+q+1;i++) scanf("%d",&gate[i]); //
    for (i=0;i<m;i++) {
        scanf("%d%d",&u,&v);
        if (lc[v]==0) lc[v] = u; // 0 is empty
        else rc[v] = u;
    }
    int maxd = 0;
    for (v=p+q+1; v<=n; v++) { // output nodes
        dp(lc[v]); // only one child
        data[v] = data[lc[v]];
        if (dep[lc[v]]>maxd) maxd = dep[lc[v]];
    }
    printf("%d\n",maxd);
    for (v=p+q+1; v<=n; v++) {
        printf("%d%c",data[v]," \n"[v==n]);
    }
    return 0;
}

### Python範例程式

以下介紹Python的範例，第一個是順向找topological sort的作法。這裡用到的資料比較多，說明如下，對於每個節點：
* data： 是該節點輸出端的信號
* gate： 是該節點的閘型態，1 ~ 4分別代表AND/OR/XOR/NOT，保留0給輸出閘
* depth： 該節點的最大延遲
* pred：該節點的前置節點(predecessor)
* succ：該節點的後繼節點(successor)
* indeg：in-degree，也就是pred的大小

第12行之前是讀入輸入資料並設定上述的相關資料。第15 ~ 22是計算一個topological sort並儲存在seq中。它的前$p$個都是輸入閘。第24 ~ 26行我們先算出最大延遲，這裡因為輸出閘本身有被記入，所以答案要減去一。
最後是計算模擬結果，其中NOT閘與輸出閘都只有一個前置節點，其他則是兩個前置節點。程式有點長，因為用到的資料比較多且四種邏輯閘分開寫。時間複雜度是點數與邊數的線性時間，因為本題每個節點的in-degree最大是2，所以邊數在點數兩倍之內。

# dag topological sort
p,q,r,m = [int(x) for x in input().split()]
n = p+q+r
data = [0]+[int(x) for x in input().split()]+[0]*(q+r)
gate = [0]*(p+1)+[int(x) for x in input().split()]+[0]*r
depth = [0]*(n+1)
pred = [[] for i in range(n+1)]
succ = [[] for i in range(n+1)]
for i in range(m):
    u,v = [int(x) for x in input().split()]
    succ[u].append(v)
    pred[v].append(u)
# find topological sort
indeg = [len(pred[v]) for v in range(n+1)]
seq = list(range(1,p+1))
head = 0
while head < len(seq):
    v = seq[head]; head += 1
    for u in succ[v]:
        indeg[u] -= 1
        if indeg[u] == 0:
            seq.append(u)
# find max depth
for v in seq[p:]: # ignore input nodes
    depth[v] = max(depth[c] for c in pred[v])+1
print(max(depth[p+q+1:])-1) # -1 for output gate
# find data
for v in seq[p:]: # ignore input nodes
    if gate[v] == 1:
        data[v] = data[pred[v][0]] & data[pred[v][1]]
    elif gate[v] == 2: 
        data[v] = data[pred[v][0]] | data[pred[v][1]]
    elif gate[v] == 3:
        data[v] = data[pred[v][0]] ^ data[pred[v][1]]
    elif gate[v] == 4:
        data[v] = 1-data[pred[v][0]]
    else: # output
        data[v] = data[pred[v][0]] 
#
print(*data[p+q+1:])

我們再給另外一種逆向的top-down DP的寫法。
其實兩種方法的道理是一樣的，top-down寫遞迴的好處是不需要先找topological sort，所以也不需要記successor與in-degree，可以省一點事，這裡我們用$data[v]<0$來表示該點還沒有計算過。此外，前置點這裡稱為child。

# topdown dp, root at output node
p,q,r,m = [int(x) for x in input().split()]
n = p+q+r
data = [-1]+[int(x) for x in input().split()]+[-1]*(q+r)
gate = [0]*(p+1)+[int(x) for x in input().split()]+[0]*r
depth = [0]*(n+1)
child = [[] for i in range(n+1)]
for i in range(m):
    u,v = [int(x) for x in input().split()]
    child[v].append(u)
#
def dp(v): # find depth and data
    if data[v]>=0: return # already done
    for u in child[v]: dp(u) # recursive call
    depth[v] = max(depth[u] for u in child[v])+1
    if gate[v] == 4: # NOT gate
        data[v] = 1-data[child[v][0]]
        return
    c1,c2 = child[v]
    if gate[v] == 1: data[v] = data[c1] & data[c2]
    elif gate[v] == 2: data[v] = data[c1] | data[c2]
    elif gate[v] == 3: data[v] = data[c1] ^ data[c2]
    #else: data[v] = data[u] # output
    return
#
for u in range(p+q+1,n+1): # each output node
    ch = child[u][0] # call its only child
    dp(ch)
    data[u] = data[ch]
    depth[u] = depth[ch]
print(max(depth[p+q+1:]))
print(*data[p+q+1:])
            

## 第四題 合併成本 (ZeroJudge m934)

### 題意分析

[(題目連結) 4.合併成本](https://zerojudge.tw/ShowProblem?problemid=m934)
有 $n$ 個數字排成一列，依序是 $a(1),a(2),\ldots a(n)$。每次可以挑選兩個相鄰的數字$u$與$v$合併，合併會花費 $|u-v|$，合併起來的數字會變為 $u+v$。問把此$n$個數字經過$n-1$合併成一個數字的最小花費是多少？以下是個例子(此圖取自ZeroJudge)。


### 演算法構思與程式流程

這是個DP的問題。因為每次只能取相鄰的兩數合併，所以過程中每一個數始終是代表**某一個連續區間的合併結果**。子問題就定義為一個連續區間$[i,j]$的最小合併成本，也就是令$dp(i,j)$是區間$[i,j]$合併成一個數的最小成本。很顯然，$dp(i,i) = 0$，因為只有一個數字不需合併。
所有可能合併的可能有非常多種，從遞迴的角度來思考最後一步是合併哪兩個區間，最後一步必然是合併$[i,k]$與$[k+1,j]$，對於某個$i\le k<j$。我們並不知道選哪個$k$最好，DP的精神就是都去算算看，從中找最小的，也就是
$$
dp(i,j) = \min_{i\le k<j} \{dp(i,k)+dp(k+1,j)+|sum(i,k)-sum(k+1,j)|\}
$$
其中$sum(i,k)$指$\sum_{p=i}^{k}a(p)$。
最後答案是$dp(1,n)$。

這一題用top-down memoization的方式是比較好寫的，如果要寫Bottom-up，子問題必須由小到大，也就是區間長度由2 到$n$的順序來計算。以下我們僅示範top-down的寫法。

### C/C++範例程式

DP往往是方法難找而程式很簡單，而且跟語言的關係不大，本題也不例外。本題以C或C\++撰寫的差異不大，以下揭示C的範例程式。程式就照著遞迴式計算，我們以二維陣列memo[i][j]來記錄cost(i,j)，並且以-1表示尚未計算過。
程式中有個細節要留意，我們在把區間切成兩段時，需要計算兩段之和的差值，因為$k$由左往右一步一步算，這個差值可以藉由先計算整段的和，然後逐步更新左邊的和，每一次只要$O(1)$就可以得到差值，請看程式的第10 ~ 13行。
另外也可以用前綴和來做。本題的輸入資料不大，如果跑到$O(n^4)$應該也可以通過。

// O(n3) DP, using (left,right) memo
#include <stdio.h>
#include <stdlib.h>
#define N 101
int memo[N][N], s[N], oo=N*10000;

int cost(int le,int ri) { // [le,ri]
    if (memo[le][ri] >=0) return memo[le][ri];
    int imin = oo, tsum=0, lsum=0;
    for (int i=le; i<=ri; i++) tsum += s[i]; // total sum
    for (int i=le; i<ri; ++i) { // [le,i] and [i+1,ri]
        lsum += s[i]; // sum of left part
        int t = cost(le,i)+cost(i+1,ri)+abs(tsum-lsum-lsum);
        if (t < imin) imin = t;
    }
    memo[le][ri] = imin;
    return imin;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i=1; i<=n; i++) {
        scanf("%d", &s[i]);
    }
    for (int i=1;i<=n;i++) for (int j=i+1; j<=n; j++)
        memo[i][j] = -1; // uncomputed
    for (int i=1; i<=n; i++) memo[i][i] = 0; // initial
	int ans = cost(1,n);
	printf("%d\n",ans);
	return 0;
}

### Python範例程式

DP往往是方法難找而程式很簡單，而且跟使用哪一種語言關係不大，本題也不例外。使用Python與C差不多。
程式就照著遞迴式計算，我們以二維陣列memo[i][j]來記錄cost(i,j)，並且以-1表示尚未計算過。
程式中有個細節要留意，我們在把區間切成兩段時，需要計算兩段之和的差值，因為$k$由左往右一步一步算，這個差值可以藉由先計算整段的和(第8行)，然後逐步更新左邊的和(第11行)，這樣平均每一次只要$O(1)$就可以得到差值(第12行)。

# top-down DP O(n^3), 0-index
n = int(input())
s = [int(x) for x in input().split()]
oo = n*10000
def cost(i,j): # min cost of [i,j]
    if memo[i][j] >= 0: return memo[i][j]
    imin = oo
    total = sum(s[i:j+1])
    lsum = 0 # sum of left part
    for k in range(i,j): # [i,k] and [k+1,j]
        lsum += s[k] 
        t = cost(i,k)+cost(k+1,j)+abs(total-lsum-lsum)
        if t<imin: imin = t
    memo[i][j] = imin
    return imin
#
memo = [[-1]*n for i in range(n)]
for i in range(n): memo[i][i] = 0
ans = cost(0,n-1)
print(ans)

另外區段和的部分也可以用前綴和來做。本題的輸入資料不大，如果跑到$O(n^4)$應該也可以通過，因為多出的那部份其實可以用sum()來寫，它雖然不是$O(1)$，但是是跑得很快的線性時間，而本題的序列長度很短。以下是個範例程式，時間複雜度是$O(n^4)$，沒有慢很多。

# top-down DP O(n^4), 0-index
n = int(input())
s = [int(x) for x in input().split()]
oo = n*10000
def cost(i,j): # min cost of [i,j]
    if memo[i][j] >= 0: return memo[i][j]
    imin = min(cost(i,k)+cost(k+1,j)+ \
            abs(sum(s[i:k+1])-sum(s[k+1:j+1])) \
            for k in range(i,j)) # [i,k] and [k+1,j]
    memo[i][j] = imin
    return imin
#
memo = [[-1]*n for i in range(n)]
for i in range(n): memo[i][i] = 0
ans = cost(0,n-1)
print(ans)

**End**