# APCS實作題2018年2月第3題：支點切割

> 日期：2024年8月22日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=f638)

## 題目

### 問題描述

輸入一個大小為 $N$ 的一維整數陣列 $p[]$ ，要找其中一個所謂的最佳切點將陣列切成左右兩塊，然後針對左右兩個子陣列繼續切割，切割的終止條件有兩個：子陣列範圍小於 $3$ 或切到給定的層級 $K$ 就不再切割。而所謂最佳切點的要求是讓左右各點數字與到切點距離的乘積總和差異盡可能的小，但不可以是兩端點，也就是說，若區段的範圍是 $[s, t]$，則要找出切點 $m \in [s+1, t-1]$，使得
$$
\left| \sum_{i=s}^t p[i] \times (i-m) \right|
$$
越小越好，如果有兩個最佳切點，則選擇編號較小的。所謂切割層級的限制，第一次切以第一層計算。
<br />

### 輸入說明

輸入格式：第一行有兩個正整數 $N$ 與 $K$。
第二行有 $N$ 個正整數代表陣列內容 $p[1] ~ p[N]$，數字間以空白隔開，總和不超過 $10^9$。$N \leq 50000$，切割層級限制 $K < 30$。
<br />

### 輸出說明

所有切點的 $p[ ]$ 值總和。
<br />

### 範例輸入1

7 1
2 4 1 3 7 6 9

### 範例輸出1

7

<br />

### 範例輸入2

7 3
2 4 1 3 7 6 9

### 範例輸出2

11

<br />

## Python 程式碼

### 寫法1，直接計算每個切割點的成本

可以通過 50%，從第10筆測資開始超時。

N, K = map(int, input().split())  # 讀取資料數量 N，切割層數上限 K
p = list(map(int, input().split()))  # 讀取資料 p
ans = 0  # 答案，預設為 0

""" 自訂函式求解，預設代入起始條件，為主要的解題過程 """
def solve(left=0, right=N-1, depth=0):
    global ans
    depth += 1  # 切割層數加 1
    if depth > K or right - left < 2: return  # 遞迴出口，切割層數大於 K 或長度小於3
    imin = 10000000000  # 最小成本，預設為很大的值
    cut = 0  # 切割點，預設為 0
    for j in range(left+1, right):  # 依序檢查以 left+1 ~ right-1 作為切割點的成本
        cost = 0  # 切割成本，預設為 0
        for i in range(left, right+1):  # 依序掃過 left ~ right
            cost += p[i]*(i-j)  # 更新 cost
        if abs(cost) < imin:  # 如果 cost 的絕對值較小
            cut = j; imin = abs(cost)  # 更新 cut 及 imin
    ans += p[cut]  # 更新 ans
    solve(left, cut-1, depth)  # 遞迴，找左半邊
    solve(cut+1, right, depth)  # 遞迴，找右半邊
""" 結束自訂函式 """

solve()  # 呼叫 solve() 求解
print(ans)  # 印出答案

<br /><br />

### 寫法2，用二維串列記錄第i個點相對於第j個點的切割成本

可以通過 50%，從第10筆測資開始，在建立 dp 二維串列時發生 MemoryError，應該是測資較大，超出記憶體上限。

N, K = map(int, input().split())  # 讀取資料數量 N，切割層數上限 K
p = list(map(int, input().split()))  # 讀取資料 p
dp = [[-1]*N for _ in range(N)]  # dp[i][j] 為第 i 個點相對於第 j 個點的切割成本，-1 代表還沒有計算過
for i in range(N): dp[i][i] = 0  # 不能以自己當作切割點，成本為 0
cuts = []  # 記錄切割點用的串列

""" 自訂函式求解，預設代入起始條件，為主要的解題過程 """
def solve(left=0, right=N-1, depth=0):
    depth += 1  # 切割層數加 1
    if depth > K or right - left < 2: return  # 遞迴出口，切割層數大於 K 或長度小於3
    imin = 10000000000  # 最小成本，預設為很大的值
    cut = 0  # 切割點，預設為 0
    for j in range(left+1, right):  # 依序檢查以 left+1 ~ right-1 作為切割點的成本
        cost = 0  # 切割成本，預設為 0
        for i in range(left, right+1):  # 依序掃過 left ~ right
            if dp[i][j] == -1: dp[i][j] = p[i]*(i-j)  # 如果還沒有計算過 dp[i][j] 的成本才需要計算
            cost += dp[i][j]  # 更新 cost
        if abs(cost) < imin:  # 如果 cost 的絕對值較小
            cut = j; imin = abs(cost)  # 更新 cut 及 imin
    cuts.append(p[cut])  # 將 p[cut] 加入 cuts
    solve(left, cut-1, depth)  # 遞迴，找左半邊
    solve(cut+1, right, depth)  # 遞迴，找右半邊
""" 結束自訂函式 """

solve()  # 呼叫 solve() 求解
print(sum(cuts))  # 印出答案

<br /><br />

### 寫法3，利用前綴和及後綴後計算切割成本

可以通過 50%，從第10筆測資超時。

N, K = map(int, input().split())  # 讀取資料數量 N，切割層數上限 K
p = [0]  # 先放入 0
p += list(map(int, input().split()))  # 讀取資料 p
p.append(0)  # 最後再補 0
psum = [0]*(N+2)  # 前綴和，兩側為 0
ssum = [0]*(N+2)  # 後綴和，兩側為 0
for i in range(1, N+1): psum[i] = psum[i-1] + p[i]  # 計算前綴和
for i in range(N, 0, -1): ssum[i] = ssum[i+1] + p[i]  # 計算後綴和
ans = 0  # 答案預設為 0

""" 自訂函式求解，預設代入起始條件，為主要的解題過程 """
def solve(left=1, right=N, depth=0):  # p 的兩端都有 0，所以預設條件為 left=1, right=N
    global ans  # 全域變數
    depth += 1  # 切割層數加 1
    if depth > K or right - left < 2: return  # 遞迴出口，切割層數大於 K 或長度小於3
    imin = 10000000000  # 最小成本，預設為很大的值
    cut = 0  # 切割點，預設為 0
    for i in range(left+1, right):  # 依序檢查以 left+1 ~ right-1 作為切割點的成本
        cost = 0  # 切割成本，預設為 0
        for j in range(left, i): cost += psum[j] - psum[left-1]  # 左側切割成本，離 i 越遠計算越多次
        for j in range(right, i, -1): cost -= ssum[j] - ssum[right+1]  # 右側切割成本，離 i 越遠計算越多次
        if abs(cost) < imin:  # 如果 cost 的絕對值較小
            cut = i; imin = abs(cost)  # 更新 cut 及 imin
    ans += p[cut]  # ans 加上 p[cut]
    solve(left, cut-1, depth)  # 遞迴，找左半邊
    solve(cut+1, right, depth)  # 遞迴，找右半邊
""" 結束自訂函式 """

solve()  # 呼叫 solve() 求解
print(ans)  # 印出答案

<br /><br />

### 寫法4，基於寫法3修改而成，減少第18 ~ 21行的計算次數

費時最久約為 1 s，使用記憶體最多約為 12.8 MB，通過測試。

N, K = map(int, input().split())  # 讀取資料數量 N，切割層數上限 K
p = [0]  # 先放入 0
p += list(map(int, input().split()))  # 讀取資料 p
p.append(0)  # 最後再補 0
psum = [0]*(N+2)  # 前綴和，兩側為 0
ssum = [0]*(N+2)  # 後綴和，兩側為 0
for i in range(1, N+1): psum[i] = psum[i-1] + p[i]  # 計算前綴和
for i in range(N, 0, -1): ssum[i] = ssum[i+1] + p[i]  # 計算後綴和
ans = 0  # 答案預設為 0

""" 自訂函式求解，預設代入起始條件，為主要的解題過程 """
def solve(left=1, right=N, depth=0):  # p 的兩端都有 0，所以預設條件為 left=1, right=N
    global ans  # 全域變數
    depth += 1  # 切割層數加 1
    if depth > K or right - left < 2: return  # 遞迴出口，切割層數大於 K 或長度小於3
    imin = 10000000000  # 最小成本，預設為很大的值
    cut = 0  # 切割點，預設為 0
    cost = 0  # 切割成本，預設為 0
    for i in range(left+1, right):  # 依序檢查以 left+1 ~ right-1 作為切割點的成本
        if i == left+1:
            cost += psum[left] - psum[left-1]  # 左側切割成本，目前只有最左側一項
            for j in range(right, i, -1): cost -= ssum[j] - ssum[right+1]  # 右側切割成本，離 i 越遠計算越多次
        else:
            cost += psum[i-1] - psum[left-1]  # 由左向右加上一項
            cost += ssum[i] - ssum[right+1]  # 由左向右刪除上一項，因為右側是用 -=，要刪除上一項反而是用 +=
        if abs(cost) < imin:  # 如果 cost 的絕對值較小
            cut = i; imin = abs(cost)  # 更新 cut 及 imin
        #print(cost)
    ans += p[cut]  # ans 加上 p[cut]
    solve(left, cut-1, depth)  # 遞迴，找左半邊
    solve(cut+1, right, depth)  # 遞迴，找右半邊
""" 結束自訂函式 """

solve()  # 呼叫 solve() 求解
print(ans)  # 印出答案

<br /><br />

## C++ 程式碼

即使改用 C++ 重寫以上的寫法1、2、3仍然會遇到同樣的問題，因此以下只列出依照寫法4修改而成的 C++ 程式碼。費時最久約為 23 ms，使用記憶體最多約為 1.3 MB，通過測試。其中有幾個需要注意的細節：
1. 第11行，引入 p、psum、ssum 這三個陣列時要用**傳參考呼叫 &**，否則執行時會超時。
2. 第14行最小成本變數 imin，第16行切割成本變數 cost，第39行前綴和 psum、後綴和 ssum，這幾個變數的格式要採用 long long，否則會溢位，得到奇怪的計算結果。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
typedef long long LL;
using namespace std;

int N, K, ans = 0;  // 資料數量 N，切割層數上限 K，ans 預設為 0

/* 自訂函式求解，預設代入起始條件，為主要的解題過程 */
void solve(int left, int right, int depth, vector<int>& p, vector<LL>& psum, vector<LL>& ssum) {
    depth++;  // 切割層數加 1
    if (depth > K || right - left < 2) return;  // 遞迴出口，切割層數大於 K 或長度小於3
    LL imin = 10000000000;  // 最小成本，預設為很大的值
    int cut = 0;  // 切割點，預設為 0
    LL cost = 0;  // 切割成本，預設為 0
    for(int i=left+1; i<right; i++) {  // 依序檢查以 left+1 ~ right-1 作為切割點的成本
        if (i==left+1) {
            cost += psum[left] - psum[left-1];  // 左側切割成本，目前只有最左側一項
            for(int j=right; j>i; j--) cost -= ssum[j] - ssum[right+1];  // 右側切割成本，離 i 越遠計算越多次
        } else {
            cost += psum[i-1] - psum[left-1];  // 由左向右加上一項
            cost += ssum[i] - ssum[right+1];  // 由左向右刪除上一項，因為右側是用 -=，要刪除上一項反而是用 +=
        }
        if (abs(cost) < imin) {  // 如果 cost 的絕對值較小
            cut = i; imin = abs(cost);  // 更新 cut 及 imin
        }
    }
    ans += p[cut];  // 更新 ans
    solve(left, cut-1, depth, p, psum, ssum);  // 遞迴，找左半邊
    solve(cut+1, right, depth, p, psum, ssum);  // 遞迴，找右半邊
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    cin >> N >> K;  // 讀取資料數量 N，切割層數上限 K
    vector<int> p (N+2, 0);  // 資料 p
    for(int i=1; i<=N; i++) cin >> p[i];  // 讀取資料 p
    vector<LL> psum (N+2, 0), ssum (N+2, 0);  // 前綴和及後綴和，兩側為 0
    for(int i=1; i<=N; i++) psum[i] = psum[i-1] + p[i];  // 計算前綴和
    for(int i=N; i>0; i--) ssum[i] = ssum[i+1] + p[i];  // 計算後綴和
    solve(1, N, 0, p, psum, ssum);  // 呼叫 solve() 求解
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`