摘要
Title: 4518. 最低票价
Tag: DP、树状数组
Memory Limit: 64 MB
Time Limit: 1000 ms

4518. 最低票价

题意

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。
在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。
每一项是一个从 1 到 365 的整数。
火车票有三种不同的销售方式：
一张为期一天的通行证售价为 costs[0] 美元；
一张为期七天的通行证售价为 costs[1] 美元；
一张为期三十天的通行证售价为 costs[2] 美元。
通行证允许数天无限制的旅行。
例如，如果我们在第 2 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。
思路

$f [ i ]$ 表示对于前 i 个天数，所需要的最小花费
我们可以将集合分成三类：
- 当前这一天 $days [ i ]$ 单独买一张一天的票，那答案就是 $f [ i ] = f [ i - 1 ] + costs [ 0 ];$
- 找到对于当前 i 最远的且刚好满足天数小于等于 7 天的下标 j，则前面的花费就是 $f [ j ]$ ，
  再加上这最近七天内的花费 $costs [ 1 ]$ ，即 $f [ i ] = f [ j ] + costs [ 1 ]$ ;
- 找到对于当前 i 最远的且刚好满足天数小于等于 30天的下标 j，则前面的花费就是 $f [ j ]$ ，
  再加上这最近三十天内的花费 $costs [ 2 ]$ ，即 $f [ i ] = f [ j ] + costs [ 2 ]$ ;
三种情况，我们取一个最小值就是答案

那么从这一天，怎么找天数相差小于等于x天且天数尽可能大呢，可以用树状数组解决，也就是前缀和，将两数中间的数量统计出来，用i减去中间隔着的数量即可

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-08-13 12:36:33
* @FilePath: \Acwing\4518\4518.cpp
* @LastEditTime: 2022-08-13 15:10:31
*/
#include <bits/stdc++.h>
using namespace std;
#define N n + 100
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

#define lowbit(x) x & -x

signed main()
{
    IOS;
    int n;
    cin >> n;
    vector<int> a(N), dp(N), cost(3), tr(366);

    auto add = [&](int x, int d) {
        for (int i = x; i < 366; i += lowbit(i))
            tr[i] += d;
    };
    auto query = [&](int x) {
        int res = 0;
        for (int i = x; i > 0; i -= lowbit(i))
            res += tr[i];
        return res;
    };
    auto get = [&](int i, int t) {
        if (a[i] - t <= 0)
            return 0LL;
        else
            return i - (query(a[i]) - query(a[i] - t));
    };

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        add(a[i], 1);
    }

    for (int i = 0; i < 3; ++i)
        cin >> cost[i];

    for (int i = 1; i <= n; ++i)
    {
        dp[i] = dp[i - 1] + cost[0];
        dp[i] = min(dp[i], dp[get(i, 7)] + cost[1]);
        dp[i] = min(dp[i], dp[get(i, 30)] + cost[2]);
    }
    cout << dp[n];
    return 0;
}

4518. 最低票价

题意

思路

代码