7/17 贪心
小组成员：吴予涵、郑荣、林育辰、许文博、刘天顺。
最优化问题考虑贪心，常见复杂度 O(n)、O(n \log n)。
求最大子段和
设 dp_i 为以 i 结尾的最大子段和。
if (dp[i - 1] >= 0) dp[i] = dp[i - 1] + a[i];
if (dp[i - 1] < 0) dp[i] = a[i];
[P1248 加工生产调度](P1248 加工生产调度 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
考虑交换加工的顺序。
假设 1 号在 2 号前放入 A 车间更优。
T = A_1 + \max(A_2, B_1) + B_2。交换后 \min(A_2, B_1) > \min(A_1, B_2)。
[P1080 [NOIP2012 提高组] 国王游戏]([P1080 NOIP2012 提高组] 国王游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
邻向交换证明正确性。
假设 i, j 相邻，设 mul 为前 i - 1 项的乘积和，a[i] 为 i 的左手数字，b[i] 为 i 的右手数字，j 同理。
假设 i 在 j 之前，则 i 所获奖金为 \frac{mul}{b_i}，j 所获奖金为 \frac{mul\times a_i}{b_j}。
则交换后 i 所获奖金为 \frac{mul\times a_j}{b_i}，j 所获奖金为 \frac{mul}{b_j}。
则有结论 \max(\frac{mul}{b_i}, \frac{mul\times a_i}{b_j}) < \max(\frac{mul\times a_j}{b_i}, \frac{mul}{b_j})，化简可得 a_i \times b_i < a_j \times b_j，由此可解此题。
[P2123 皇后游戏]
同 [P1080 [NOIP2012 提高组] 国王游戏 ，可解得交换后 a_j = a_i 时，\min(a_j, b_i) > \min(a_i, b_j)，a_j \not= a_i 时，a_j > a_i。