發表新討論
#33102: 解題報告


dfd8282@gmail.com (fishhh)

學校 : 嘉義市私立嘉華高級中學
編號 : 99760
來源 : [140.114.59.162]
最後登入時間 ：
2024-11-13 00:16:45
f173. m6a1-作物種植(Plant) -- TOI練習賽2020年6月潛力組 | From: [36.236.10.17] | 發表日期 : 2022-11-30 21:06
設 dp[i][j]={}; 代表到第 i 個路段之前(包含第 i 個) 以及道路盡頭為 j 時的最大可種植面積
 
那麼dp 轉移式就是 dp[i][j] = max(dp[i-1][j],dp[i-1][第 i 個路段的開頭]+第 i 個路段的種植面積);
如果 j < 第 i 個路段的開頭 那麼 dp[i][j] = dp[i-1][j] 就好

但是 這題要建dp表前要把你的所有路段sort過一次
 
還要做滾動dp 不然記憶體會爆掉喔~
 
一部分程式碼
for(int i=1;i<=t;i++){
        for(int j=0;j<=m;j++){
            if(j>=v[i-1].second){
                dp[i%2][j]=max(dp[1-(i%2)][j],dp[1-(i%2)][v[i-1].first]+(v[i-1].second-v[i-1].first));
            }
            else{
                dp[i%2][j]=dp[1-(i%2)][j];
            }
        }
    }
 
ZeroJudge Forum