written on 2022-08-17
打得还可以虽然又是倒一hh
前三题中第一题贪心稍微注意一下，想了一段时间还算可以。
可以看一下第四题。这题最大的启示就是：要求的东西只关注最后的形状而不关注过程，因此过程是可以乱排的，为了方便求解，对于这种题我们不妨将其按升序或者降序的方式放置，这样的话状态就会很清晰明确。
具体到这道题，思路还是很巧妙的，解法也很多，这里介绍一种相对好理解的方法。
以下默认元素从小到大插入。
显然是 \(O(n^2)\) 的 dp，然后第一维肯定是当前放到了哪个数。考虑第二维，这里我们将第二维设为目前序列中存在的不合法元素个数，注意这里定义的不合法元素指的是既非山峰又非山谷的那些点（很妙的状态吧）。那么最终的答案就是 \(f_{n,0}\)。
然后这里考虑一次放置对不合法元素个数的影响，显然如果将新的元素放在不合法元素的旁边的话，就一定会减少一个不合法元素，可以手动模拟造一组样例试一下，可以发现，如果原不合法元素数量为 \(x\) 个，那么这样的位置也就是有 \(x\) 个。
接着考虑使其不变的部分，这时我们应当敏锐地察觉到，要求的数列是一个波动数列。根据这个性质，显然，如果在中间（不包括之前说的不合法元素边上的那 \(x\) 个点）插入元素的话，由于其波动性，插入一个元素一定会使不合法元素个数 \(+1\) ，所以我们只考虑两边的情况，由于两边的元素一定不可能是不合法元素（根据我们的定义），所以分类讨论，如果是山峰，那么向内插入元素一定不会构成不合法元素；如果是山谷，向外插入同理，同样可以手动模拟一下，很好理解。
那么剩下的就是会使其增加的了，总共 \(i+1\) 个空，剩下的空就有 \(i+1-x-2=i-x-1\) 个，这些点均可以使其增加。
分类讨论找出决策后，动态规划的转移就不难了，详见代码。
\(E\) 题 好题，和练习68的 \(E\) 以及 P3211 都有异曲同工之妙，结合了高斯消元，不过这题的不同在于需要使用 AC自动机，快速匹配多字符串失配时的情况，具体贴一下别人的题解，可以学习一下。
\(F\) 题的状态去重很烦没搞懂就不管了
标签：元素,一下,可以,练习,个数,合法,插入,ZLOJ,69 From： https://www.cnblogs.com/Freshair-qprt/p/16623445.html