PI-計算服務需要的時間

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;
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *