爱生气的书店老板 - 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)

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