蓝桥杯5130 健身

问题描述

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

他有 m 个健身计划，对于第 i 个健身计划，需要连续的  天，如果成功完成，可以获得健身增益 si​ ，如果中断，得不到任何增益。

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

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

输入格式

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

第二行输入 q 个整数，t1,t2,t3...tq​ ，代表有其他安排的日期。

接下来 m 行，每行输入两个整数 ki,si​ 。代表该训练计划需要  天，完成后可以获得 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≤m≤50 ， 1≤si≤ ， 0≤ki≤20 ， 1≤t1<t2<...<tq≤n 。

 

 

完全背包问题，枚举空闲段天数，每一段使用完全背包

问题转化

• 每个健身计划 i 是一个“物品”：

  • 体积：v[i]（需要的天数）。

  • 价值：w[i]（健身增益）。

• 背包容量：day[k]（当前区间的可用天数）。

• 目标：在不超过 day[k] 的情况下，选择若干健身计划（可重复），使总价值最大。

状态转移

• f[j] = max(f[j], f[j - v[i]] + w[i])：

  • f[j]：不选当前计划。

  • f[j - v[i]] + w[i]：选当前计划，剩余天数 j - v[i] 的最优解加上当前价值。

#include<iostream>
#include<cmath>
#include<algorithm>#define int long long
using namespace std;const int N = 2e5+10;
int n, m, q;
int k[N];
int t[N];  //存储由其他安排的日期  
int v[N], w[N];
int day[N];  //day[i]：第i个区间的可用天数
int dp[N];  //dp[i]：表示用 i 天能获得的最大增益
int ans;signed main()
{cin>>n>>m>>q;for(int i=1; i<=q; ++i) cin>>t[i];for(int i=1; i<=m; ++i) cin>>k[i]>>w[i];//计算每个区间的可用天数t[0]=1, t[q+1]=n;  //为了计算day[i]赋的值 for(int i=q+1; i>0; --i){if(i==1 || i==q+1) day[i] = t[i] - t[i-1];else day[i] = t[i] - t[i-1]-1;} //计算每个健身计划需要的连续天数 for(int i=1; i<=m; ++i){v[i]= pow(2, k[i]);}for(int i=1; i<=q+1; ++i)  //遍历每个可健身区间{for(int j=1; j<=m; ++j)  //遍历每个健身计划{for(int p=v[j]; p<=day[i]; ++p){dp[p] = max(dp[p], dp[p-v[j]] + w[j]);}}ans += dp[day[i]];}cout<<ans;return 0;
}