正经题解｜解题赛

题目大意

题目给出$n$个题目(题目编号从1开始)第一次解题的得分$a_i$与后续解题分数$b_i$，并且给出你能够解题的题目总数$k$，要求你计算出最大可以获取的分数总额。

题意分析

我们需要在$k$次的解题机会当中，选择一个积分最大化的方案执行，最后输出答案即可。

但是在题目当中，我们的方案搭配有很多种，比如选择只做第一个题目，做第一个题目之后只做第二个题目等。

解题思路

根据题目意思，我们可以很快总结出两种大致最值的策略。

• 先做完所有的任务，拿取第一次的奖励之后，再将剩下的机会花在重复解题价值最高的题目当中。
• 找到重复做价值最大的谜题，然后一直做它。

这两种策略的取舍和状态具有很多种，但是我们也将答案锁定在了一个较小的范围当中，那么如何进行解题呢？我们还可以再一次进行优化。

我们不妨可以思考一下，我们可以同时枚举出这两种策略所涉及到的所有方案，然后选取出其中总价值最大的答案即可。

我们可以设定一个变量$temp$，来保存第一次做过每一个任务的积分，同时设定一个变量$max_{bi}$，来保存重复做价值最高的任务。

根据$k$,枚举我们做到第$i$个任务时，剩下的机会$k - i$全部兑换$b_i$的积分后，所获得的总积分$temp + b[i] * (k - i)$。

最终，我们从我们枚举的所有总积分当中选取出一个最大值即可。

时间复杂度解析

本题仅使用for循环对数组进行遍历，因此时间复杂度为$O(n)$

代码演示

#include<bits/stdc++.h>
using namespace std;
int arr[200005];
int brr[200005];
void solve()
{
	int n,k;
	cin >> n >> k;
	for(int i = 1 ; i <= n ; i ++ )
	{
		cin >> arr[i];
	}
	for(int j = 1;  j <= n ; j ++ )
	{
		cin >> brr[j];
	}
	int answer ;
	int temp;
	int max_bi ;
	answer = temp = max_bi = 0;
	for(int i = 1 ; i <= min(n,k) ; i ++ )
	{
		temp += arr[i];
		max_bi = max(max_bi,brr[i]);
		answer = max(answer,temp + (k - i) * max_bi);
	}
	cout << answer << endl;
	
}

int main()
{
	solve();
	return 0;
}