Jimmy 作为一名 SCUT 的大学生,自然需要去学习。 在 SCUT,Jimmy 的课表上有 N 门不同的课程,在学期的每一周内他总共会上 N 次课,每一门课程恰好一周上一次课,Jimmy 对于每一个课程都有一个熟练度,初始时都为 0。 对于一节课 Jimmy 可以选择如下两种选项之一: 1. 去上课:如果 Jimmy 选择去上课,此时他对于这节课的熟练度增加 AiAi。 2. 翘课:Jimmy 热爱学习,因此他会在翘课的时候找地方自学,此时他对于这节课的熟练度增加 BiBi。 为了去学习更多的课外知识,Jimmy 不会在其余时间学习这 N 门课程,但是他又不想要让自己的成绩排名靠后,于是他找到了你,请你帮忙让他在每周恰好翘 k 门课时,他所有课程熟练度总和尽可能大。 输入格式 第一行两个整数 N, k 接下来一行 N 个整数 AiAi。 接下来一行 N 个整数 BiBi。 输出格式 仅输出一行一个整数,表示 Jimmy 在每周恰好翘 k 门课时所有课程熟练度总和的最大值。用c++实现,时间限制2s,内存限制256MB,N最大值是10000000
时间: 2024-02-06 07:11:48 浏览: 24
根据题目数据范围,我们可以发现 $N$ 可能会很大,因此需要对原来的二维动态规划进行优化。
首先,可以发现 $f[i][j]$ 只与 $f[i-1][j]$ 和 $f[i-1][j-1]$ 有关,因此可以使用滚动数组将空间复杂度优化为 $O(k)$。
其次,对于每一门课程,选择上课和选择翘课,可以分别看作是在原有基础上增加了 $a_i+b_i$ 和 $b_i$ 的贡献,因此可以将 $a_i+b_i$ 和 $b_i$ 分别存储到两个数组中,然后使用差分的思想将问题转化为一个区间翻转的问题。
具体思路如下:
1. 定义 $f[j]$ 表示翘了 $j$ 门课时,所有课程熟练度总和的最大值。
2. 初始化 $f[0] = 0$。
3. 对于每一门课,使用差分思想将 $a_i+b_i$ 和 $b_i$ 的贡献分别存储到两个数组中。
4. 对于每一门课,从 $k$ 到 $1$ 枚举翘课的门数 $j$,更新 $f[j]$:
- 如果 $j$ 恰好等于 $k$,则需要将 $a_i+b_i$ 的贡献加到 $f[j]$ 中。
- 否则,需要将 $b_i$ 的贡献加到 $f[j]$ 中,并且使用差分的思想更新 $f[j]$ 和 $f[j-1]$。
5. 最终答案为 $\max\limits_{i=0}^k f[i]$。
时间复杂度为 $O(nk)$,空间复杂度为 $O(k)$。
下面是用 C++ 实现的代码:
```c++
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e7 + 10;
int n, k;
int a[N], b[N];
int f[N];
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ ) cin >> b[i];
for (int i = 1; i <= n; i ++ ) a[i] += b[i];
memset(f, 0xcf, sizeof f);
f[0] = 0;
for (int i = 1; i <= n; i ++ )
for (int j = k; j >= 1; j -- )
{
if (j == k) f[j] += a[i];
else
{
int t = f[j];
f[j] = max(f[j], f[j - 1] + b[i]);
f[j - 1] = max(f[j - 1], t + a[i] - b[i]);
}
}
int res = -1e9;
for (int i = 0; i <= k; i ++ )
res = max(res, f[i]);
cout << res << endl;
return 0;
}
```