【蓝桥】健身

一、题目

1、题目描述

小蓝要去健身，它可以在接下来的 1 ~ $n$ 天中选择一些日子去健身。

它有 $m$ 个健身计划，对于第 $i$ 个健身计划，需要连续的 $2^{k_i}$ 天，如果成功完成，可以获得健身增益 $s_i$，如果撞断，得不到任何增益。

同一个健身计划可以多次完成，也能多次获得收益，但是同一天不能同时完成两个或两个以上的健身计划。

但是它的日程表中有 $q$ 天有其它安排，不能去健身，问如何安排健身计划，可以使得 $n$ 填的健身增益和最大。

输入格式

第一行输入三个整数 $n,m,q$。

第二行输入 $q$ 个整数，$t_1,t_2,t_3...t_q$ ，代表有其他安排的日期。

接下来 $m$ 行，每行输入两个整数 $k_i,s_i$。代表该训练计划需要 $2^{k_i}$ 天，完成后可以获得 $s_i$ 的健身增益。

输出格式

一个整数，代表最大的健身增益和。

样例输入

10 3 3
1 4 9
0 3
1 7
2 20
1
2
3
4
5

样例输出

30
1

说明

在样例 2 ~ 3 天进行计划2，5 ~ 8 天进行计划3，10 ~ 10 天进行计划1。

评测数据范围
数据范围：$1\le q\le n\le 2\times 10^5$， $1\le m\le 50$，$1\le s_i\le 10^9$，$0le{k}_i\le 20$，$1\le t_1<t_2<...<t_q\le n$

2、基础框架

#include 
using namespace std;
int main()
{
  // 请在此输入您的代码
  return 0;
}
1
2
3
4
5
6
7

3、原题链接

健身

二、解题报告

1、思路分析

首先可以确定，对于 $k$ 值相同的时候，可能存在多个增益，所以对于每一个相同的 $k$ 值，只保留最大的增益值即可。

代码中使用 sw[k] 来表示需要锻炼 $2^k$ 天的计划可以得到的最大增益。

使用 dp[i] 表示训练到 $i$ 天可以得到的最大增益值。

转移方程如下：

如果当前这一天不训练，或者不能训练，那么 $dp[i]=dp[i-1]$ 。

然后考虑当前这一天是某个计划结束的一天，即连续 $2^k$ 天进行了这个计划，则在 $2^k$ 天前的最大收益加上当前这个计划的收益 sw[k]，就是训练到 $i$ 天得到的最大收益，即 $dp[i]=dp[i-2^k]+sw[k]$ ，那么需要满足第 $i-2^k+1$ 天到第 $i$ 天都是空闲的。

如何快速计算在某个区间段是否空闲呢？使用前缀和算法，使用 $sum[i]$ 来表示前 $i$ 天有多少个不空闲的时间，那么我们使用 $sum[r]-sum[l-1]$ 是否等于 $0$ 就可以判断区间是否空闲。

最后 $dp[n]$ 即是答案。

2、时间复杂度

$O(n\times max(k_i))$

3、代码详解

#include 
#include 
using namespace std;

int main()
{

    int n, m, q;
    cin >> n >> m >> q;

    int sum[n + 1];
    memset(sum, 0, sizeof(sum));

    int sw[25];
    memset(sw, 0, sizeof(sw));

    long long dp[n + 5];
    memset(dp, 0, sizeof(dp));

    int x;

    for (int i = 1; i <= q; i++) {
        cin >> x;
        sum[x]++;
    }

    //前缀和
    for (int i = 1; i <= n; i++) {
        sum[i] += sum[i - 1];
    }

    int k, s;

    for (int i = 1; i <= m; i++) {
        cin >> k >> s;
        sw[k] = max(sw[k], s); //k相同的情况，只记录最大收益
    }

    for (int i = 1; i <= n; i++) {

        //情况1：第i天不锻炼
        dp[i] = dp[i - 1]; 

        //情况2：第i天是某个计划锻炼的最后一天
        for (int k = 0; k <= 20; k++) { //确定哪个计划是合法的
            int start = i - (1 << k); //从哪天开始的当前这个计划，即2^k天以前
            if ((start >= 0) && (sum[i] - sum[start] == 0)) { //合法的开始天数，且连续的2^k天都是空闲的
                dp[i] = max(dp[i], dp[start] + sw[k]);
            } else {
                break;
            }
        }
    }

    cout << dp[n] << endl;
  	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57