[CF1499C] Minimum Grid Path - 贪心

Description

n×n的矩阵，让你从 (0,0) 走到 (n,n)，每次只能向上走或者向右走且步长至少为1，而且走完之后必须换方向，最多换n-1次方向，也就是走n段路，每段都都有一个权值，这段路的计算代价为这次走的长度×这段路的权值 \(c[i]\)，求最小的代价

Solution

奇数偶数分开考虑，显然是相互独立的，对于一个部分，我们一定将最小的那个代价分配尽可能多，剩下的长度全是 \(1\)

特别注意“至少”

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    int n;
    cin >> n;
    vector<int> c(n + 2);
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    int sum[2] = {0, 0}, mx[2];
    memset(mx, 0x3f, sizeof mx);
    int res = 1e18;
    for (int i = 1; i <= n; i++)
    {
        sum[i & 1] += c[i];
        mx[i & 1] = min(mx[i & 1], c[i]);
        if (i >= 2)
        {
            int ans = 0;
            if (i & 1)
            {
                ans += sum[1] - mx[1];
                ans += (2 * n - i + 1) / 2 * mx[1];
                ans += sum[0] - mx[0];
                ans += (2 * n - i + 3) / 2 * mx[0];
            }
            else
            {
                ans += sum[1] - mx[1];
                ans += (2 * n - i + 2) / 2 * mx[1];
                ans += sum[0] - mx[0];
                ans += (2 * n - i + 2) / 2 * mx[0];
            }
            res = min(res, ans);
        }
    }
    cout << res << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)
        solve();
}