#33102: 解題報告
dfd8282@gmail.com
(fishhh)
設 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]; } } }