瞌睡

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

方法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)输出知识点最大值.

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

3. 代码：

   #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)输出知识点最大值.

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

3. 代码：

   #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;
   }