9月25日YLOI总结

T1 变幻	T2 交替	T3 打拳	T4 扑克
耗时:30min 得分:100pts	耗时:45min 得分:40pts	耗时:60min 得分:20pts	耗时:1h45min 得分:0pts

解题思路

一道DP题， $dp_{i,j}$ 表示遍历到第 $i$ 个数、一共变小了 $j$ 个数且第 $i$ 个数为山谷数时，所有山谷数的最大和。

设 $g_{i,j} = \max_{k = 1}^{i}dp_{k,j}$ ，则状态转移方程为 $\begin{cases} 当 a_{i-1} > a_i \$

计算贡献。先打个贡献的表，使用超大眼观察法可以发现每个数的贡献与杨辉三角有关。

易知，“布呗之路”的位置其实对答案没有影响，故不妨固定“布呗之路”的位置，将答案乘 $2^n$ 。
此时再做状压DP，可以求出共有多少种方案。

大大模拟太恶心了，写不了一点。