You've successfully subscribed to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your billing info is updated.
Billing info update failed.

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

【动态规划】

### Example:

输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3



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

### Analysis

v[i]：在时刻 i 时满意的客人数量， 则

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

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

$$x[i]=x[i-1] + v[i]$$

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

$$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.$$

### Solution 【动态规划】 ( 10ms)

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]);
}
}