1421D - Hexagons (贪心)

清疚 2021-07-16 18:45 287阅读 0赞

[题目][Link 1]

思路：将此坐标转化为直角坐标系（纵坐标，横坐标），然后将六条路径优化，上cs = min(c6, c5 + c1), 下cx = min(c3, c4 + c2), 左cz = min(c5, c4 + c6), 右cy = min(c2, c3 + c1)。因为还有右上、右下的路径，所以干脆一并优化了 cys = min(c1, cy + cs), czs = cz + cs, cyx = cy + cx, czx = min(c4, cz + cx);//cys右上 czs 左上… 然后直接计算即可，详细看代码。

Code:

#include<iostream>
    #include<queue>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    
    int main()
    { 
        int t;cin >> t;
        while (t--)
        { 
            int x, y;cin >> y >> x;
            ll c1, c2, c3, c4, c5, c6;cin >> c1 >> c2 >> c3 >> c4 >> c5 >> c6;
            ll cs = min(c6, c5 + c1), cx = min(c3, c4 + c2), cz = min(c5, c4 + c6), cy = min(c2, c3 + c1);//cs上 cx下 cz左 cy右
            ll cys = min(c1, cy + cs), czs = cz + cs, cyx = cy + cx, czx = min(c4, cz + cx);//cys右上 .....
            if (x >= 0 && y >= 0)
            { 
                ll c = min(x, y);
                x -= c, y -= c;
                cout << c * cys + x * cy + y * cs << endl;
            }
            else if (x >= 0 && y < 0)
            { 
                y = abs(y);
                ll c = min(x, y);
                x -= c, y -= c;
                cout << c * cyx + x * cy + y * cx << endl;
            }
            else if (x < 0 && y < 0)
            { 
                y = abs(y);x = abs(x);
                ll c = min(x, y);
                x -= c, y -= c;
                cout << c * czx + x * cz + y * cx << endl;
            }
            else if (x < 0 && y >= 0)
            { 
                y = abs(y);x = abs(x);
                ll c = min(x, y);
                x -= c, y -= c;
                cout << c * czs + x * cz + y * cs << endl;
            }
        }
    }

[Link 1]: https://codeforc.es/problemset/problem/1421/D