【动态规划】
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% 的用户
|
|
复杂度分析
时间: O(n)
若不优化 sum 的存储,每次都重新计算,则为 O(n*X)
空间:O(1)