1821F

传送门 solution 对于一个确定的树木种植位置方案 \(\{x\}\)，我们规定树木优先向左侧倒下。 枚举有 \(p\) 个树木向右倒，然后我们要求每个向右倒的树木左侧不能有连续 \(k\) 个空格。设 \(f_{i}\) 表示有 \(p\) 个树木向左倒，恰好有 \(i\) 个能向左倒的树木 ......

考虑如何判断一个方案是合法的，很容易想到贪心，从左到右考虑第 $i$ 棵树： - 如果这棵树能向左倒即 $[x_i-k,x_i]$ 没有被占据，就向左倒。 - 否则向右倒。 显然向左倒对之前已经倒下的树没有影响，而对后面的树来讲，这棵树向左倒能留下尽量多的空间，所以优先向左倒一定不劣。 所以考虑一个 ......

$$逐渐变成自己最讨厌的样子$$ 首先考虑 $dp$，设 $dp_{i,j}$ 表示当前放了 $i$ 个树，目前不得不覆盖到的最右点为 $j$，每放一棵树，如果能往左就往左，否则往右倒。 $\text{GF}$ 首先考虑 $dp_{i,j}$ 的转移。 第一种，在 $[j+1,j+k]$ 放一个树， ......