题解 | M. 龙卷风摧毁停车场

M. 龙卷风摧毁停车场

笔者出的题，观察到我们只需要记录招式 的使用次数 ，以及是否使用招式

招式 一定是最后使用的，招式 的顺序无所谓

对于给定的出招序列 ，我们在已知 的情况下，可以比较 的优劣性

若 ，招数 更优，直接一次大招做完

反之，计算 可分成多少块 ，还余下多少，即

对于 份 ，我们使用更优的招数 ；对于余下的 ，我们比较 和 取最小值即可

该过程的时间复杂度为

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

typedef long long ll;

#define fType int
#define foreach(x, a, b) for (fType x = a, _end_ = b; x <= _end_; x++)
#define foreach_sub(x, a, b) for (fType x = a, _end_ = b; x >= _end_; x--)
#define tpl make_tuple

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    ll H, d1, t1, d2, p, t2, C;
    cin >> H >> d1 >> t1 >> d2 >> p >> t2 >> C;

    ll ans = C * H;
    foreach (c2, 0, H)
    {
        ll h = H - (c2 * (c2 - 1) / 2 * p + c2 * d2);
        if (h <= 0)
        {
            ans = min(ans, c2 * t2);
            break;
        }

        if (t1 >= C * d1)
        {
            ans = min(ans, c2 * t2 + C * h);
        }
        else
        {
            ll x = h / d1, y = h % d1;
            ans = min(ans, c2 * t2 + x * t1 + min(C * y, t1));
        }
    }

    cout << ans << "\n";

    return 0;
}

扩展思考：定义 为招数 使用 次情况的最小代价，这是一个单峰函数吗？能否三分？