题目难度：二星
考察点：贪心、前缀和

方法1：暴力算法

  1. 分析：
    我们首先可以通过一次遍历获取小易醒着时所获得的知识点分值，即时所获得的分值，由于题目要求我们只需要进行一次叫醒活动，那么我们就选择当前小易是睡着即的时刻进行往后k个枚举，循环n次即可，然后每次枚举判断其是否为知识点分的最大值。

算法实现：
(0). 首先计算小易清醒时所能获得的知识点分值，记作tot。c
(1). 然后从i到n进行遍历，当小易睡着时即b[i]=0时，j从i时刻一直枚举到i+k-1时刻，如果中间还有b[j]=0的情况，那么就记录加和知识点，即将时刻区间[i,i+k-1]种b[i]=0的知识点相加，然后在加上之前的清醒时的知识点分值tot，比较最大值。
(2)输出知识点最大值.

  1. 复杂度分析：
    时间复杂度：O(n^2)
    空间复杂度：O(n)

  2. 代码：

    #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5+5;
int a[MAXN], b[MAXN], sum[MAXN];
int main() {
 int n, k; cin>>n>>k ;
 for(int i=1; i<=n; i++) cin>>a[i];
 int tot = 0;
 for(int i=1; i<=n; i++) {
     cin>>b[i];
     if(b[i]) tot += a[i];
 }
 int ans = tot;
 for(int i=1; i<=n; i++) {
     if(b[i] == 0) {
         int tmp = 0;
         for(int j=0; j<k; j++) {
             if(i + j > n) break;
             if(b[i+j] == 0) tmp += a[i+j];
         }
         ans = max(ans, tot+tmp);
     }
 }
 cout<<ans<<endl;
 return 0;
}

方法2：前缀和算法

  1. 分析：
    根据之前的算法我们进行优化，分析一下究竟是什么导致了时间复杂度这么高呢？其实从1到n进行枚举，这个显然是不能在优化的，那么我们对于第二层循环进行优化，因为我们要计算的是区间[i,i+k-1]的睡着的知识点的分值，那么我们可以用一个前缀和数组sum存储，sun[i]表示从[1,i]区间小易睡着的知识点分值，那么对于之前枚举的[i,i+k-1]的睡着知识点分值就可以表示为 sum[i+k-1]-sum[i-1]，然后在计算知识点分值最大值即可。

算法实现：
(0). 首先计算小易清醒时所能获得的知识点分值，记作tot，同时计算前缀和数组。
(1). 然后从i到n进行遍历，对于每一个时刻i来说（为了简化，可以不用特殊计算b[i]==0的情况），我们计算tot+ sum[i+k-1]-sum[i-1]的值即可，对于这些值取最大值即可。
(2)输出知识点最大值.

  1. 复杂度分析：
    时间复杂度：O(n)
    空间复杂度：O(n)

  2. 代码：

    #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5+5;
int a[MAXN], sum[MAXN];
int main() {
 int n, k; cin>>n>>k;
 for(int i=1; i<=n; i++) cin>>a[i];
 int tot = 0;
 for(int i=1; i<=n; i++) {
     int t; cin>>t;
     if(t) tot += a[i];
     sum[i] = sum[i-1] + a[i]*(1-t);
 }
 int ans = tot;
 for(int i=1; i<=n; i++) {
     int ed = min(n, i+k-1);
     int tmp = (sum[ed]-sum[i-1]);
     ans = max(ans, tmp+tot);
 }
 cout<<ans<<endl;
 return 0;
}