louisfghbvc的部落格

題目連結:  https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=14418

題目大意:  問你從左下角到右上角，需要最少花費多少能到。

思路:  等價於左上角到右下角，觀察水管1, 3, 5，可以發現5 > 3 > 1 cost最佳，比如直線6，你一定放5，1(cost 25)不會放3，3(cost 26)，所以根本是貪心法。

。不管怎麼走，路徑長都是l+w-1。

那基本上分成2種case，左上角走到左下角。左下角走到終點。

                                   左上角走到右上角，右上角再到終點。

2種取最小。

那直線距離，水管會放吧，先放5，再放3，再放1，貪心放法。

代碼:  

#include <bits/stdc++.h>  
using namespace std;  
  
int greedy(int x){  
    int cost = 0;  
    if(x >= 5){  
        cost += 20 * (x/5);  
        x %= 5;  
    }  
    if(x >= 3){  
        cost += 13 * (x/3);  
        x %= 3;  
    }  
    if(x >= 1){  
        cost += 5 * (x/1);  
        x %= 1;  
    }  
    return cost;  
}  
  
int main()  
{  
    int t, l, w;  
    cin >> t;  
    while(t--){  
        cin >> l >> w;  
        printf("%d\n", min(greedy(w-1)+greedy(l), greedy(w)+greedy(l-1)));  
    }  
}