Leetcode 1388. Pizza With 3n Slices

[Wizmann]

Problem Code

题意

给你一个循环数组，数组长度为3*N。每一轮拿走一个数，并删除和它相邻的两个数（然后把剩下的元素再结成环）。

问N轮之后，你能取走的所有数之和最大为多少。

解法

这题其实是道结论题，我就非常好奇这些结论都是哪里来的。。。

首先我们要证明取走N个任意非连续的数都是可行的。因为3N个数里面，我们要取走N个，剩下2N个都是被删除的。又因为有至少一个要取走的数的左邻居或右邻居有至少2个要被删除的数，所以删除这个数之后，我们就把原有的问题缩减了规模。

例如：N = 2时，有排列"XOXOOO"和"XOOXOO"（X为要取走的数，O为要删除的数）。此时一定有足够多的O可以被删除。

剩下的就比较简单了。只需要注意数组是循环的，第一个和最后一个数不能同时取。