coding_black

APCS 2023年10月 解題思緒+參考作法

寫完題目之後的一些見解

這次的題目跟過往的題目難度進行對比的話,會發現難度降低滿多的,基本上只要有一定的作題量,面對題目時應該都會有些想法。

第一題:算是基本題型,只需要使用for迴圈+變數+條件判斷式即可完成作答,就算複雜一點使用陣列+排序也可以完成,算是固定給學生的甜甜福利題。

第二題:一如既往地出了模擬與矩陣題,本題概念上並不複雜,就是很簡單的配對問題,只是配對完之後要記得使用Memoization(備忘錄法)的技巧輔以記憶,那由於是第二題也不太需要去注意時間複雜度的問題,只要你的寫法不要太過…..誇張?就好。

第三題:標準的graph(圖論)相關的題目,可以使用DFS(深度優先搜尋法)或者BFS(廣度優先搜尋法)方式進行解答,除此之外也有其他方法,但筆者認為用graph的方法解答會比較簡單。而這題由於記憶體的限制問題會比較推崇BFS的寫法。

第四題:只要有想法就很簡單的題目,k=0與k>0的思路會稍稍有點不一樣需要注意到。當k=0時就是很簡單的數學問題,可以依靠prefix Sum(前綴和)的方式配合檢查總金額是否小於0,最後紀錄金額最大值即可。而k>0時就是標準的背包問題,不過這題的數字有點大若使用python解答沒有去稍微優化的話可能也無法過關。

想看我其他解題影音的可以看這裡

Leetcode75 Level1

想了解CodingBar看這裡

CodingBar

ZeroJudge題目

  1. 機械鼠
  2. 卡牌遊戲
  3. 搬家
  4. 投資遊戲

機械鼠

題目簡述:
在一條數線上有 n 個食物,而有一隻老鼠在 x 位置上。
老鼠會根據食物的多寡決定往左或者是往右走,但一定是往多的地方走且不可回頭。
當老鼠吃完食物後會在哪個位置上?
輸入第一行含兩個正整數 x 跟 n ,x代表老鼠初始座標,n代表食物的數量。
輸入第二行有 n 個正整數,每個正整數會隔一空格,代表食物在數線上的位置(不會按照順序排列)
輸出共一行含兩個正整數中間需隔一空格,第一個正整數為最多能吃到的食物數目,第二個為最後一個吃到的食物位置。
可以參考以下的示意圖。

大致上如圖示,你會看到老鼠先在一個位置上站好,而糧食在第二行輸入時不會按照順序排序,因此在讀取時順序會是亂七八糟的。

這題算是一題滿基礎的題目,做法也相當多樣化,至少可以有二種作法,那我這邊都會一一介紹。

機械鼠第一個做法 :利用紀錄 + 比大小

首先我先介紹比較優的解法,利用比較大小以及紀錄吃的食物數量來進行處理。
我們首先要去思考題目要的東西是什麼呢 -> 一共有兩個東西:1. 最多的食物 2. 最後吃的食物位置
那要怎麼知道左邊的食物比較多還是右邊的食物比較多呢 -> 用兩個變數紀錄往左邊吃多少往右邊吃多少
要怎麼紀錄最左邊的食物或是最右邊的食物 -> 用兩個變數,一個紀錄最大值一個紀錄最小值
根據以上想法應該可以做出如下的程式碼。

#Python
x,n = [int(i) for i in input().split()]
numList = [int(i) for i in input().split()]#把食物座標存到numList
maxNum,minNum = -101,101#食物的最大座標、食物的最小座標
left,right = 0,0#往左右吃的食物數量
for i in numList:#讀取食物座標 i:食物座標 X:老鼠座標
    if i > x:#食物在老鼠右邊
        right = right + 1#右邊食物多一
        maxNum = max(maxNum,i)#比較老鼠右邊的座標大小
    if i < x:#食物在老鼠左邊
        left = left + 1
        minNum = min(minNum,i)
if left > right:#左邊食物較多
    print(left,minNum)
else:
    print(right,maxNum)
//C++
#include <iostream>
using namespace std;
int main(){
    int x,n;
    cin>>x>>n;
    int maxNum,minNum;
    int left,right;
    maxNum = -101;//食物的最大座標
    minNum = 101;//食物的最小座標
    left = right = 0;//往左右吃的食物數量
    for(int i = 0;i<n;i++){//temp:食物座標 X:老鼠座標
        int temp;
        cin>>temp;//直接進行輸入食物座標
        if (temp>x){//食物在老鼠右邊
            right++;//右邊食物多一
            if(temp>maxNum){//比較老鼠右邊的座標大小
                maxNum = temp;
            }
        }
        if (temp<x){//食物在老鼠左邊
            left++;//左邊食物多一
            if(temp<minNum){//比較老鼠左邊的座標大小
                minNum = temp;
            }
        }
    }
    if (left > right){//左邊食物較多
        cout<<left<<" "<<minNum;
    }else{
        cout<<right<<" "<<maxNum;
    }
} 

機械鼠第二個做法 :排序

接下來是排序的這個方法,想法很簡單,既然數線沒有排列好那我們就幫他排列,並且把老鼠的位置也放進去,會形成以下圖形,此時就沒有先後問題。

此時我們只需要做以下事情:
1. 知道老鼠在這個數列裡面的索引值
2. 透過索引值即可知左邊吃多少,右邊吃多少
3. 比較左右哪邊吃比較多決定輸出第0個座標或是最後一個座標

#Python
x,n = [int(i) for i in input().split()]
numList = [int(i) for i in input().split()]
numList.append(x)
numList.sort()
index = numList.index(x)#可用二搜代替
if index > n - index:
    print(index,numList[0])
else:
    print(n-index,numList[-1])
//C++
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    int x, n;
    cin >> x >> n;

    vector<int> numList(n);
    for(int i = 0; i < n; ++i) {
        cin >> numList[i];
    }

    numList.push_back(x);
    sort(numList.begin(), numList.end());

    int index = find(numList.begin(), numList.end(), x) - numList.begin();

    if (index > n - index) {
        cout << index << " " << numList[0] << endl;
    } else {
        cout << n - index << " " << numList.back() << endl;
    }

    return 0;
}

卡牌遊戲

題目簡述:
有一個n x m的表格裡面填滿了數字,每個數字剛好出現兩次。
消除兩個相同數值相同且中間沒有阻隔其他障礙物的數字 x 時可以獲得 x 分。
可以垂直或者平行消除,但中間不可阻隔其他數值。
可參考以下示意圖

共有偶數種數字,分散在表格的各個地方,找出相鄰的數字並消除它們

這題在矩陣裡算是一題滿基本的題目,只要能夠正常地讀取矩陣,應該都寫得出這一題,這邊提供兩種做法。

卡牌遊戲第一個做法:只處理「列」 + 旋轉矩陣

首先這題目其實分成上下兩子題
第一子題為60% n = 1,也就是說只有一列的狀況

如果從一般的視角來去觀察這題的話應該會產生如上圖的狀況,但由於我們是跑程式讀取東西時基本上都是由左至右讀取,因此這題其實可以搭配stack的技巧產生出以下的效果。

如此一來就有了「只有一列」的解決方案,因此若我們把這方案由上往下執行一次,就可以完成所有列的分數加總。
但此時就會遇到下一個問題:「行」的部分要怎麼處理呢?我這邊的解決方案為行列對調,只要把行變成列,再用相同作法做一遍即可。接著就是不斷執行此過程,直到分數沒有增加為止。
這樣做法的最大好處是,完全不用擔心行列搞混,我們只要專注在行的處理就可以了。

#Python
def reGroup(matrix,score):
    flag = 0
    newMaxtrix = []
    for numList in matrix:
        numList = list(numList)
        stack = []
        for i in range(len(numList)):#讀取numList裡面的東西
            if numList[i] == -1:
                continue
            if stack:
                if stack[-1][-1] == numList[i]:
                    index,value = stack.pop()
                    numList[i],numList[index] = -1,-1
                    score += value
                    flag = 1
                else:
                    stack.append((i,numList[i]))
            else:
                stack.append((i,numList[i]))
        newMaxtrix.append(numList)
    return newMaxtrix,score,flag
n,m = [int(i) for i in input().split()]
matrix = [[int(j) for j in input().split()] for i in range(n)]
matrix,result,no = reGroup(matrix,0)
flag = 1
if n == 1:
    print(result)
else:
    while flag:
        matrix = list(zip(*matrix))
        matrix,temp,flag = reGroup(matrix,0)
        result += temp
    print(result)
//C++
#include <iostream>
#include <vector>
using namespace std;
//行列對調
vector<vector<int>> transMatrix(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    // 創建一個新的二維 vector 來存儲轉置後的矩陣
    vector<vector<int>> transposedMatrix(cols, vector<int>(rows));
    for(int i = 0; i < rows; ++i) {
        for(int j = 0; j < cols; ++j) {
            // 將原始矩陣的行元素設置為新矩陣的列元素
            transposedMatrix[j][i] = matrix[i][j];
        }
    }
    return transposedMatrix;
}
long long getAns(vector<vector<int>>& matrix){
    int flag = 1;
    long long score = 0;
    do {
        
        for (auto &numList : matrix) {
            vector<int> indexStack;
            vector<int> valueStack;
            for (int i = 0; i < numList.size(); i++) {
                if (numList[i] == -1) continue;
                if (!indexStack.empty()) {
                    if (valueStack.back() == numList[i]) {
                        int index = indexStack.back(); indexStack.pop_back();
                        int value = valueStack.back(); valueStack.pop_back();
                        numList[i] = numList[index] = -1;
                        score += value;
                        flag = 1;
                    } else {
                        indexStack.push_back(i);
                        valueStack.push_back(numList[i]);
                    }
                } else {
                    indexStack.push_back(i);
                    valueStack.push_back(numList[i]);
                }
            }
        }
        matrix = transMatrix(matrix);
        if(flag == 0){
            break;
        }
        flag = 0;
    }while(1);
    return score;
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> matrix(n, vector<int>(m));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            cin >> matrix[i][j];
        }
    }
    long long result;
    result = getAns(matrix);
    cout<<result;
} 

卡牌遊戲第二個做法:行列一同處理,處理右邊以及下邊

以一個單元為基準,向右向下慢慢對照。

基本上來說與第一個做法沒有差太多,但個人認為「行」的處理比「列」麻煩,因此我首選不是這個做法。

#Python
n,m = [int(i) for i in input().split()]
matrix = [[int(j) for j in input().split()] for i in range(n)]
# read matrix and add sentinel
score = 0
while True:
    flag = 0
    for i in range(n):
        stack1 = []#右
        for j in range(m):
            if matrix[i][j] == -1:
                continue
            #右
            if stack1:
                if stack1[-1][-1] == matrix[i][j]:
                    index,value = stack1.pop()
                    matrix[i][j],matrix[i][index] = -1,-1
                    score += value
                    flag = 1
                else:
                    stack1.append((j,matrix[i][j]))
            else:
                stack1.append((j,matrix[i][j]))
            #下
            stack2 = []#下
            for si in range(i,n):
                if matrix[si][j] == -1:
                    continue
                if stack2:
                    if stack2[-1][-1] == matrix[si][j]:
                        index,value = stack2.pop()
                        matrix[si][j],matrix[index][j] = -1,-1
                        score += value
                        flag = 1
                    else:
                        stack2.append((i,matrix[si][j]))
                else:
                    stack2.append((i,matrix[si][j]))
    if flag == 0:
        break
print(score) 
//C++
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> matrix(n, vector<int>(m));
    
    // 讀取矩陣
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            cin >> matrix[i][j];
        }
    }

    int score = 0;
    bool flag;

    do {
        flag = false;
        // 遍歷矩陣的每一行
        for(int i = 0; i < n; ++i) {
            vector<pair<int, int>> stack1; // 用於檢查向右
            
            for(int j = 0; j < m; ++j) {
                if(matrix[i][j] == -1) continue;
                // 檢查向右
                if(!stack1.empty() && stack1.back().second == matrix[i][j]) {
                    pair<int, int> top = stack1.back();
                    stack1.pop_back();
                    matrix[i][j] = matrix[i][top.first] = -1;
                    score += top.second;
                    flag = true;
                } else {
                    stack1.emplace_back(j, matrix[i][j]);
                }

                // 檢查向下
                vector<pair<int, int>> stack2; // 用於檢查向下
                for(int si = i; si < n; ++si) {
                    if(matrix[si][j] == -1) continue;
                    if(!stack2.empty() && stack2.back().second == matrix[si][j]) {
                        pair<int, int> top = stack2.back();
                        stack2.pop_back();
                        matrix[si][j] = matrix[top.first][j] = -1;
                        score += top.second;
                        flag = true;
                    } else {
                        stack2.emplace_back(si, matrix[si][j]);
                    }
                }
            }
        }
    } while(flag); // 若 flag 為 false,則終止循環

    cout << score << endl;

    return 0;
}

搬家

題目簡述:
有一 n x m 的矩陣,有七種水管會至於矩陣當中,求水管最多連通多少格?


基本上只要看到這種算格子的題目都會是屬於Graph相關題型,而且通常可以用BFS(廣度優先搜尋法)或者DPS(深度優先搜尋法)進行解決。

如同這張圖示,受先第一個連通管為XH7JHL共六個,第二個連通管有H7I共三個,第三個連通管有IXIIXJ共六個,第四個連通管有HH共二個,第五個連通管有HHJ共三個,第六個連通管有I共一個。因此最多就只有六格連通管。

這題在解題的時候有DFS跟BFS的方式可以解題,但當看到1<=n,m<=500時就要注意到空間複雜度的問題,因此左右衡量後還是決定使用BFS會比較穩妥。

搬家BFS解法

這題解題重點在於兩點
1. 水管可以連通的方向 -> 利用map的方式限定可以走的方向
2. 連通管形成迴路時的處理方式 -> 紀錄走過的地方
照我這樣寫看起來會比較清楚,但缺點是時間複雜度會偏高,執行效率會比較低一點。
制定完之後接下來要跑的就是正常的BFS的流程。

#Python
#X:上下左右
#I:上下
#H:左右
#L:右上
#7:左下
#F:右下
#J:左上
#0:沒有水管
#要確認是否連通
n,m = [int(i) for i in input().split()]
matrix = [list(input()) for i in range(n)]#矩陣
d = {"I":[(-1,0),(1,0)],"H":[(0,1),(0,-1)],"L":[(-1,0),(0,1)],"7":[(0,-1),(1,0)],"F":[(1,0),(0,1)],"J":[(0,-1),(-1,0)],"X":[(1,0),(0,1),(-1,0),(0,-1)]}
#d為各連通管可以連通之方位
d2 = {(1,0):"XILJ",(-1,0):"XI7F",(0,1):"XH7J",(0,-1):"XHLF"}
#d2為該方位可以連通到的連通管
maxScore = 0
for i in range(n):
    for j in range(m):
        if matrix[i][j] != "0":
            queue = [(i,j,d[matrix[i][j]])]
            matrix[i][j] = "0"
            pointer = 0
            while pointer < len(queue):
                x,y,direction = queue[pointer]
                for dir in direction:
                    newX,newY = x+dir[0],y+dir[1]
                    if 0 <= newX < n and 0 <= newY < m and matrix[newX][newY] in d2[(dir[0],dir[1])]:
                        queue.append((newX,newY,d[matrix[newX][newY]]))
                        matrix[newX][newY] = "0"
                pointer += 1
            maxScore = max(maxScore,len(queue))
print(maxScore)
//C++
//並非最優寫法
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <tuple>

using namespace std;

// 助手函數來輸出最大得分
void printMaxScore(int n, int m, vector<vector<char>>& matrix) {
    map<char, vector<pair<int, int>>> d = {
        {'I', {{-1, 0}, {1, 0}}},
        {'H', {{0, 1}, {0, -1}}},
        {'L', {{-1, 0}, {0, 1}}},
        {'7', {{0, -1}, {1, 0}}},
        {'F', {{1, 0}, {0, 1}}},
        {'J', {{0, -1}, {-1, 0}}},
        {'X', {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}}
    };
    
    map<pair<int, int>, string> d2 = {
        {{1, 0}, "XILJ"},
        {{-1, 0}, "XI7F"},
        {{0, 1}, "XH7J"},
        {{0, -1}, "XHLF"}
    };

    int maxScore = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (matrix[i][j] != '0') {
                queue<tuple<int, int, vector<pair<int, int>>>> q;
                q.push(make_tuple(i, j, d[matrix[i][j]]));
                matrix[i][j] = '0';
                int currentScore = 0;
                
                while (!q.empty()) {
                    auto [x, y, direction] = q.front();
                    q.pop();
                    ++currentScore;
                    
                    for (auto& dir : direction) {
                        int newX = x + dir.first;
                        int newY = y + dir.second;
                        if (newX >= 0 && newX < n && newY >= 0 && newY < m && 
                            d2[{dir.first, dir.second}].find(matrix[newX][newY]) != string::npos) {
                            q.push(make_tuple(newX, newY, d[matrix[newX][newY]]));
                            matrix[newX][newY] = '0';
                        }
                    }
                }
                maxScore = max(maxScore, currentScore);
            }
        }
    }
    cout << maxScore << endl;
}

int main() {
    int n, m;
    cin >> n >> m;
    cin.ignore(); // 忽略在讀取整數輸入後的換行符
    vector<vector<char>> matrix(n, vector<char>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> matrix[i][j];
        }
    }

    printMaxScore(n, m, matrix);
    return 0;
}
 

搬家DFS解

個人嘗試後是不建議使用DFS解,確實會有空間的問題,因此這邊我只附上Python解法。

n, m = [int(i) for i in input().split()]
matrix = [list(input()) for _ in range(n)]  # 矩陣

# 各類型水管可連通的方向
d = {
    "I": [(-1, 0), (1, 0)],
    "H": [(0, 1), (0, -1)],
    "L": [(-1, 0), (0, 1)],
    "7": [(0, -1), (1, 0)],
    "F": [(1, 0), (0, 1)],
    "J": [(0, -1), (-1, 0)],
    "X": [(1, 0), (0, 1), (-1, 0), (0, -1)]
}

# 從給定方向可連接的水管類型
d2 = {
    (1, 0): "XILJ",
    (-1, 0): "XI7F",
    (0, 1): "XH7J",
    (0, -1): "XHLF"
}

# 執行 DFS 的函數
def dfs(x, y):
    if not (0 <= x < n and 0 <= y < m) or matrix[x][y] == "0":
        return 0
    
    # 計算這塊水管
    count = 1
    pipe_type = matrix[x][y]
    matrix[x][y] = "0"  # 標記為已訪問
    
    # 探索所有可連通方向
    for dx, dy in d[pipe_type]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] in d2[(dx, dy)]:
            count += dfs(nx, ny)
    return count

# 遍歷每個單元格以找到最大的連通管群
max_score = 0
for i in range(n):
    for j in range(m):
        if matrix[i][j] != "0":
            max_score = max(max_score, dfs(i, j))

print(max_score)
 

投資遊戲

題目簡述:
你擁有一個長度為 n 的陣列,代表每天的投資收益,以及 k (k<=20)張金牌。

你可以自行決定投資的開始和結束日期。在你選擇投資的每一天,你可以選擇消耗一張金牌來跳過當天,或者不使用金牌而拿取當天的收益。你的目標是找出如何投資,以實現最大的總收益。

請注意,你只能在投資期間進出一次。

算是一個滿基本的dp(動態規劃)題目,直接用動態規劃的方式進行解答可以得到快速且簡短的解答。
但個人在審題的時候還是習慣去注意到一些小細節,畢竟我們重點是來拿分的,而不是要求自己一定要做出多完美的答案,因此我們還是來注意一下「子題分數」這一part吧。

子題分數:
20%:滿足 k = 0,且 1<=n<=2000。
 20%:滿足 k = 0,且 1<=n<=150000。
60%:滿足 1<=k<=20,1<=n<=150000。
你會看到前40%其實是沒有使用到金牌的,那如果沒有使用到金牌的話,那其實有沒有使用到dp這麼方法就無所謂了。因此針對前40%我使用了其他的技巧來完成它。

投資遊戲40%解法(zerojudge可到50%)

在思考的時候我們可以把它當成一個線圖來去看,每一格都會有可以賺到的錢或者當天會賠的錢,那我們要做的事情就是把每一天的錢加起來變成一個總和—-有點像是prefix sum的技巧,但在加起來的同時也要注意到是否會變成「負債」的狀態,如果會負債的話,代表前幾天賺得錢毫無意義,因此就直接歸0重新開始,遇到可以賺錢的時候再重新進行加總即可。最後找出每次從0開始後的最高峰即可。

#Python
n,k = [int(i) for i in input().split()]
numList = [int(i) for i in input().split()]
total = 0
maxScore = 0
for i in range(len(numList)):
    total = max(total,0) + numList[i]
    maxScore = max(total,maxScore)
print(maxScore)
//C++
#include <iostream>
#include <vector>
#include <algorithm> // std::max 函數需要引入此標頭檔
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> numList(n); // 建立一個大小為 n 的向量來儲存數字
    for (int i = 0; i < n; ++i) {
        cin >> numList[i];
    }

    int total = 0;
    int maxScore = 0; 
    for (int num : numList) {
        total = max(total, 0) + num;
        maxScore = max(total, maxScore);
    }

    std::cout << maxScore << std::endl;

    return 0;
}

投資遊戲100%解法(Dynamic Programing)

在寫動態規劃相關題目的時候,我們務必要去找出上下項的關聯性,通常這是一個很麻煩的過程,但只要能夠成功地找出來的話程式碼其實就很好寫了,也因此我們來構思一下這個部分。
首先我們要先了解以下幾點:
1. 金牌不一定要使用
2. 金牌是有限的
3. 整個數列裡可能不到k個負值
了解以上幾點後我們再來思考該動態規劃的遞迴式應該要如何完成,首先我們先來看40%的。
(以下部分為何會放置在100%裡說明,因個人淺見,就算沒思考到以下部分也應回答得出40%解法)

total = max(total,0) + numList[i]

這部分程式碼其實是已經簡化完畢的,total理論上來說他應該會是一個陣列用來儲存每日營利用

也就是說我們可以知道說 total[i] = max(total[i],0) + numList[i]
這其實已經是遞迴的一個環節,它代表的就是指 0 張金卡的狀況。
(至於為何可以化為total一個變數呢?因為我們只使用得到目前的高峰值,其他東西用不到可以省略呀!)
那接下來100%的部分該怎麼思考呢?先來畫個表格吧!
先假設共有2張金卡,接下來 i 會用來表示到第幾天,j 是使用的金卡
此時的思考模式要略有一點變化,我需要為每天使用金卡的狀況建立表格,因為金卡有限。若未來遇到新數據時且需要使用金卡時,但發現金卡前面已經用光了,可是又發現這次數據是比之前的數據更值得使用金卡的,那前面沒有使用表格(recMatrix)進行紀錄就很尷尬。

這時候大體沒什麼需要注意的,因為都是正數據,只需要好好地保存即可。

此時出現了一個負數據,根據目前可以使用的金卡去進行保存。

第二個負數據出來了,此時就可以開始去思考,表格上的數字到底是從哪裡出來的。
像是k=0的部分會去比較,前一天加上今天的數據 與 0加上今天的數據誰比較大,可以很單純地得到以下程式碼

recMatrix[i][0] = max(recMatrix[i-1][0],0) + numList[i]

那有金卡時又該如何處理負數據呢?數字又該從哪裡抓呢?我們先來專注於 k=1 時 4 這個數字的產生吧!
這時候其實會有個分歧路線,因為這是第二個負數據,那我們必須決定要扛哪個負數據,因此我們有兩個選擇。
1. 選取前一天沒有使用金卡時的金額 -> 這代表今天要使用金卡
2. 選取前一天已經使用一張金卡時的金額並扣掉今天的負數據 -> 這代表了我們認為扛住今天的負數據比較賺
那很明顯這次我們選擇了第二個方案,因為上次若沒有使用金卡,那就算今天使用金卡也依然為0;反之若我們選擇在上次使用金卡,而今天扛住負數據還會有 4 的收益,根據上述可以推論出下面的程式碼。

recMatrix[i][1] = max(recMatrix[i][0], recMatrix[i][1] + numList[i])
#recMatrix[i][0] 代表前天沒使用金卡,今天使用,所以不需要加上今天的數據
#recMatrix[i][1] + numList[i] 代表前天使用了金卡,今天不能使用,所以要加上今天的數據

那其實是到如今也已經把所有該思考的東西思考完畢,接著只要建立好遞迴式即可。但我還是把整個圖表列出來吧。

列出圖表這在考試時是非常有用的,考試時間這麼多,絕對可以很悠閒畫個圖的。
好了既然已經完成的話,我們就列出程式碼吧!

n,k = [int(i) for i in input().split()]
newNumList = [int(i) for i in input().split()]
recMatrix = [[0 for j in range(k+1)] for i in range(len(newNumList)+1)] #建立儲存用的矩陣
#以下的解法改編自40%解法,只不過把total用成矩陣去進行統計
maxScore = 0
for i in range(len(newNumList)):
    recMatrix[i+1][0] = max(recMatrix[i][0],0) + newNumList[i] # 0張金卡
    # 這部分你會發現到與40%部分一樣
    for j in range(1,k+1):#1~K張金卡
        recMatrix[i+1][j] = max(recMatrix[i][j-1],recMatrix[i][j] + newNumList[i])
        #比較用了金卡(左邊)和不用金卡(右邊)誰比較大,把大的存下來
    maxScore = max(recMatrix[i+1][k],maxScore) #比較前面的最大值跟現在的最大值誰大
print(maxScore)

若一般的狀況下我會說已經完成了,但APCS通常對於Python會比較嚴格,因此略為進行一些改良。
以下改良兩個部分
1. 把所有負數據中間的正數據先加一起 -> 因為金卡不會影響正數據的計算
2. 把矩陣變成兩個數列相互交換 -> 因為更前面的數據已經用不到了,那不如釋放出來增加計算效能。

#Python
n,k = [int(i) for i in input().split()]
numList = [int(i) for i in input().split()]
newNumList = []#為了減少時間複雜度,先幫必正的部分進行加總處理
t = 0
for i in range(n):
    if numList[i]<0:
        newNumList.append(t)
        newNumList.append(numList[i])
        t = 0
    else:
        t += numList[i]
if t >=0:
    newNumList.append(t)
recList1,recList2 = [[0]*(k+1) for i in range(2)] #建立儲存用的矩陣
#以往都會用一個滿版的 (k+1)^2矩陣,但APCS對於Python比較嚴格,所以還是稍微節省一點會比較好
#以下的解法改編自40%解法,只不過把total用成矩陣去進行統計
maxScore = 0
for i in range(len(newNumList)):
    recList2[0] = max(recList1[0],0) + newNumList[i] # 0張金卡
    # 這部分你會發現到與40%部分一樣
    for j in range(1,k+1):#1~K張金卡
        recList2[j] = max(recList1[j-1],recList1[j] + newNumList[i])
        #比較用了金卡(左邊)和不用金卡(右邊)誰比較大,把大的存下來
    maxScore = max(recList2[k],maxScore) #比較前面的最大值跟現在的最大值誰大
    recList1,recList2 = recList2,recList1 #對調準備重做
print(maxScore)
//C++
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> numList(n);
    for (int i = 0; i < n; ++i) {
        cin >> numList[i];
    }

    vector<int> newNumList;
    int t = 0;
    for (int i = 0; i < n; ++i) {
        if (numList[i] < 0) {
            if (t > 0) {
                newNumList.push_back(t);
                t = 0;
            }
            newNumList.push_back(numList[i]);
        } else {
            t += numList[i];
        }
    }
    if (t > 0) {
        newNumList.push_back(t);
    }

    vector<int> recList1(k+1, 0), recList2(k+1, 0);
    int maxScore = 0;
    for (int i = 0; i < newNumList.size(); ++i) {
        recList2[0] = max(recList1[0], 0) + newNumList[i];
        for (int j = 1; j <= k; ++j) {
            recList2[j] = max(recList1[j - 1], recList1[j] + newNumList[i]);
        }
        maxScore = max(recList2[k], maxScore);
        recList1.swap(recList2); // 對調以進行下一輪迭代
    }
    
    cout << maxScore << endl;
    return 0;
}
 

探索更多來自 CodingBar 專欄文章 的內容

立即訂閱即可持續閱讀,還能取得所有封存文章。

Continue reading