2022.11.11 AM 12:00 by CBJ
來源 : https://drive.google.com/file/d/1CMnis82zw9hGQHW1pRv3LFXACoUGA90Y/view 出題者 : 108資訊學科能力競賽複賽-彰雲嘉 標籤 : DP(動態規劃) 難易度 : 6
解題想法 : 預先定義兩個陣列， cost[i][j] 定義為第i個人完成第j個服務時累積的時間 self[i][j] 定義為第i個人需要在第j個櫃台待多久(= 輸入的資料 ) 對於第i個人是否能進行第j個服務只跟自己或前一個人有關 : 1.跟自己有關 : 自己還在接受第j-1個服務,所以不能去第j個 2.跟前一個有關 : 前一個人還在第j個服務當中 根據題意，當1和2都結束以後，才有辦法接受第j個服務。 因此自己完成第j個服務的時間 = max(完成j-1時累積的時間, 前一個人完成j時累積的時間) + 自己完成j所需要的時間 轉換成剛剛定義的兩個陣列就變成 : cost[i][j] = max(cost[i][j-1], cost[i-1][j]) + self[i][j] 得出的這個式子就是DP最重要之一的轉移式了。 再來還要定義初始狀態 : 因為人和服務都是從1開始算，所以不會有第0個人，也就是說第0個人完成任何服務時累積的時間都是0，還有，所有人在第0個櫃台也都不會花任何時間(因為沒有這個櫃台)，所以 cost[i][0] = cost[0][j] = 0 如此一來，我們就可以得出最終答案，根據定義，它應該會位在cost[N][K]的位置(最後一個人完成最後一個服務時累積的時間)，只要輸出它即可。
//C++ language
//solution link(含註解): https://github.com/CBJ0519/CBJsProgramDiary.com/blob/main/%E8%B3%87%E8%A8%8A%E5%AD%B8%E7%A7%91%E8%83%BD%E5%8A%9B%E7%AB%B6%E8%B3%BD/108%E5%BD%B0%E9%9B%B2%E5%98%89/PI-%E8%A8%88%E7%AE%97%E6%9C%8D%E5%8B%99%E9%9C%80%E8%A6%81%E7%9A%84%E6%99%82%E9%96%93.cpp
#include<iostream>
#define MAXN 1000
#define MAXK 1000
using namespace std;
int cost[MAXN][MAXK];
int self[MAXN][MAXK];
int main(){
int N,K;
cin>>N>>K;
for(int i=1;i<=N;i++){
for(int j=1;j<=K;j++){
cin>>self[i][j];
}
}
for(int i=0;i<=N;i++){
cost[i][0]=0;
}
for(int j=0;j<=K;j++){
cost[0][j]=0;
}
for(int i=0;i<=N;i++){
for(int j=0;j<=K;j++){
cost[i][j]=max(cost[i-1][j],cost[i][j-1])+self[i][j];
}
}
cout<<cost[N][K]<<"\n";
return 0;
}
發佈留言