1. 爱生气的书店老板 - Grumpy Bookstore Owner

【动态规划】

Problem Link

今天,书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客(customers[i])会进入书店,所有这些顾客都会在那一分钟结束后离开。

在某些时候,书店老板会生气。 如果书店老板在第 i 分钟生气,那么 grumpy[i] = 1,否则 grumpy[i] = 0。 当书店老板生气时,那一分钟的顾客就会不满意,不生气则他们是满意的。

书店老板知道一个秘密技巧,能抑制自己的情绪,可以让自己连续 X 分钟不生气,但却只能使用一次。

请你返回这一天营业下来,最多有多少客户能够感到满意的数量。

Example:

示例:

输入:customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出:16
解释:
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

提示:

  • 1 <= X <= customers.length == grumpy.length <= 20000
  • 0 <= customers[i] <= 1000
  • 0 <= grumpy[i] <= 1

Analysis

定义:

v[i]:在时刻 i 时满意的客人数量, 则

$$\begin{equation}v[i]=\left{​ \begin{array}{lr}​ \text{0,}&\quad\text{如果书店老板生气:grumpy[i] = 1,}\​ \text{customers[i],} &\quad\text{如果书店老板不生气:grumpy[i] = 0.}​ \end{array}\right.\end{equation} $$

即:$v[i] = customers[i] & (grumpy[i] - 1)$

这里使用位操作计算,也可以基于判断操作

x[i]: 在时间 $[0, i]$ 内,未使用防止暴脾气时的最大满意值 ,则

$$\begin{equation}x[i]=x[i-1] + v[i]\end{equation} $$

y[i]: 在时间 $[0, i]$ 内,使用防止暴脾气后的最大满意值。则

$$\begin{equation}y[i]=max\left{\begin{array}{lr}v[i]+y[i-1]&\quad\text{时刻 i 技能已经结束,}\sum\limits_{k=i-X+1}^{i}(customers[k]) + x[i-X]&\quad\text{时刻 i 技能未结束,按恰好结束计算即取最大.}\end{array}\right.\end{equation}$$

最终结果为:$y[i]=max{x[end_time], y[end_time]}$

Solution 【动态规划】 ( 10ms)

执行用时: 10 ms, 在Grumpy Bookstore Owner的Java提交中击败了100.00% 的用户

内存消耗: 48.6 MB, 在Grumpy Bookstore Owner的Java提交中击败了100.00% 的用户

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int X) {
        int len = customers.length;
        int[] x = new int[len];
        int[] y = new int[len];
        /* base case */
        x[0] = customers[0] & (grumpy[0] - 1);
        y[0] = customers[0];
        int sum = customers[0];    // 优化使用技能期间的满意顾客总数
        /* dp */
        for (int i = 1; i < len; i++) {
            int v = customers[i] & (grumpy[i] - 1);
            x[i] = v + x[i-1];
            if (i < X) {
                sum += customers[i];
                y[i] = Math.max(y[i-1] + v, sum);
            } else {
                sum += customers[i] - customers[i-X];
                y[i] = Math.max(y[i-1]+ v, x[i-X] + sum);
            }
        }
        return Math.max(x[len-1], y[len-1]);
    }
}

复杂度分析

时间: O(n)

若不优化 sum 的存储,每次都重新计算,则为 O(n*X)

空间:O(1)