【蓝桥】健身

【蓝桥】健身

一、题目

1、题目描述

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

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

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

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

输入格式

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

第二行输入 q q q 个整数， t 1 , t 2 , t 3 . . . t q t_1, t_2, t_3...t_q t1​,t2​,t3​...tq​ ，代表有其他安排的日期。

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

输出格式

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

样例输入

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

样例输出

30

说明

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

评测数据范围
数据范围： 1 ≤ q ≤ n ≤ 2 × 1 0 5 1 \le q \le n \le 2 \times 10^5 1≤q≤n≤2×105， 1 ≤ m ≤ 50 1\le m \le 50 1≤m≤50， 1 ≤ s i ≤ 1 0 9 1 \le s_i \le 10^9 1≤si​≤109， 0 l e k i ≤ 20 0 le k_i \le 20 0leki​≤20， 1 ≤ t 1 < t 2 < . . . < t q ≤ n 1 \le t_1 \lt t_2 \lt ... \lt t_q \le n 1≤t1​<t2​<...<tq​≤n

2、基础框架

#include <iostream>
using namespace std;
int main()
{// 请在此输入您的代码return 0;
}

3、原题链接

健身

二、解题报告

1、思路分析

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

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

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

转移方程如下：

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

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

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

最后 d p [ n ] dp[n] dp[n] 即是答案。

2、时间复杂度

O ( n × m a x ( k i ) ) O(n \times max(k_i)) O(n×max(ki​))

3、代码详解

#include <iostream>
#include <cstring>
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;
}