寫完題目之後的一些見解
這次的題目跟過往的題目難度進行對比的話,會發現難度降低滿多的,基本上只要有一定的作題量,面對題目時應該都會有些想法。
第一題:算是基本題型,只需要使用for迴圈+變數+條件判斷式即可完成作答,就算複雜一點使用陣列+排序也可以完成,算是固定給學生的甜甜福利題。
第二題:一如既往地出了模擬與矩陣題,本題概念上並不複雜,就是很簡單的配對問題,只是配對完之後要記得使用Memoization(備忘錄法)的技巧輔以記憶,那由於是第二題也不太需要去注意時間複雜度的問題,只要你的寫法不要太過…..誇張?就好。
第三題:標準的graph(圖論)相關的題目,可以使用DFS(深度優先搜尋法)或者BFS(廣度優先搜尋法)方式進行解答,除此之外也有其他方法,但筆者認為用graph的方法解答會比較簡單。而這題由於記憶體的限制問題會比較推崇BFS的寫法。
第四題:只要有想法就很簡單的題目,k=0與k>0的思路會稍稍有點不一樣需要注意到。當k=0時就是很簡單的數學問題,可以依靠prefix Sum(前綴和)的方式配合檢查總金額是否小於0,最後紀錄金額最大值即可。而k>0時就是標準的背包問題,不過這題的數字有點大若使用python解答沒有去稍微優化的話可能也無法過關。
想看我其他解題影音的可以看這裡
想了解CodingBar看這裡
ZeroJudge題目
機械鼠
題目簡述:
在一條數線上有 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,也就是說只有一列的狀況
如此一來就有了「只有一列」的解決方案,因此若我們把這方案由上往下執行一次,就可以完成所有列的分數加總。
但此時就會遇到下一個問題:「行」的部分要怎麼處理呢?我這邊的解決方案為行列對調,只要把行變成列,再用相同作法做一遍即可。接著就是不斷執行此過程,直到分數沒有增加為止。
這樣做法的最大好處是,完全不用擔心行列搞混,我們只要專注在行的處理就可以了。
#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(深度優先搜尋法)進行解決。
這題在解題的時候有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;
}