省流
赛时一个半小时没出题，赛后再来三个小时终于搞出 A。
10.5
内含剧透，请vp后再来。
不是题解！！！！！！！
赛前
本来发现要补的东西还剩很多，结果当天上午就补完了前一天的 \(ABC\)，下午又搞了两道区域赛题，想着晚上打 \(ARC\) 和 \(CF\)。结果到赛前发现 \(CF\) 竟然是凌晨 \(00:35\) 开始，被震惊了一下，最后就决定只打 \(ARC\) 了。
赛时
先看第一题，也只看了第一题。题目给了 \(n\) \((n\leq100)\) 个商品，每个商品都有一个很大价格，然后有一个总钱数 \(x\)，要求每秒买一个物品，每过一秒所有商品的价格减一，到零为止，求购买完所有商品不同顺序有多少种。
看到这个范围很容易想到 \(n^4\) 的 \(DP\)，进而考虑怎么把很大的范围变成 \(n\) 的范围。发现其实可以看作总花费是 \(\sum_{a_i}^n\)，然后减去一些减掉的价格。第 \(i\) 个位置买第 \(j\) 个商品减免的花费其实就是 \(min(a_j, i - 1)\)，这样就把所有数据范围都缩到 \(n\) 这个级别，容易想到 \(DP\) 的三维分别是当前位置 \(i\)，与购买了哪些相关的 \(j\) 和减免的价值 \(k\)，\(k\) 的范围总之小于 \(n^2\)，具体就是求和前 \(n-1\) 个数。最后取减免的花费大于等于原总花费和拥有的钱数之差的情况数。
显然这里面最需要设计的就是那个 \(j\)，毕竟你不可能来一个状压存 \(2^{100}\)。我一开始是选择存了当前到第 \(i\) 位的总情况数，\(j\) 是当前位中以第 \(j\) 个商品结尾的情况数，结果发现这样存其实只是把同一个商品不能连续拿而不是我们想要的只能拿一次。
此时发现取商品的顺序应该是可以动刀的，毕竟这个量的大小顺序应该会非常好用，但不知道排序后该怎么设计，在赛中 \(100min\) 左右逃跑了，遂寄。
赛后
因为打挂了没熬夜打 \(CF\)，第二天起来发现 \(qwsxza\) 竟然上黄了，而我现在差距还很大，而昨天满打满算也就学了 \(7h\) 左右，就这样我还在以打挂了心情不好为借口逃避，非常失败了。
继续看 A 题，重新理清思路之后可以发现一个重要的性质，就是
减免的花费其实就是 \(min(a_j, i - 1)\)
再加上排序这个想法，状态的设计就不言自明了（其实还是很难想）。我们只取考虑较小的那个放到较大的花费，如对位置考虑时就把所有该位置放较大数的情况都加上位置的花费，而放较小数则无视。同理对一个商品考虑时只加上该商品放较大位置时的花费，放较小位置则因为已经在考虑这个较小位置的时候加过了就不需要再管了。
那么排序之后我们就可以按照上面的思路搞一下。对于一个位置，我们把商品，也就是题目中的灯分成三类，小灯，中灯和老灯，分别表示这个商品的价格小于，等于和大于这个位置的编号减一。我们的状态就统计当前 \(i\) 位置中已经塞入了 \(j\) 个小灯时减免花费为 \(k\) 的情况有多少个。
首先我们转移 \(i\)。一个新的位置进来时，可以往这个位置里放小灯或者中老灯，如果放小灯那么减免花费已经在后面算小灯（等一下还要转移灯）时统计过了，就 \(i+1\) 和 \(j+1\) 直接转相应的 \(k\) 就行。如果加入的是中老灯，那么 \(j\) 不变，\(k\) 则要增加 \(i - 1\)，因为不管放置哪个中老灯的效果都一样，所以可以放置的种类就是现在剩余的中老灯数量。
在转移过 \(i\) 之后，我们要把和 \(i - 1\) 相等的中灯全部转移了。中灯同样有两种放法，一种是放到小于等于的位置上，一种是放到大于的位置上。和位置的转移一样，如果放到比较小的位置，那么直接 \(j+1\) 就可以了，因为这个放置的花费 \(k\) 在前面转移中老灯时已经计算过了。如果放到大于的位置上，那么当前 \(i\) 个位置的小灯数 \(j\) 就不变，而增加的 \(k\) 同样都是 \(i-1\)，且后面大于的位置都可以放，也就是种类是 \(n - i\)。
需要注意的是转移某个灯的时候，一定要静态的转移再赋值，否则放置的数量会左脚踩右脚上天，以及开的数组不要太大了，在本地虽然不会影响编译但内存的分配方面可能出诡异的问题，平常能写还是节省空间开个滚动数组更好。
现在还是太摆了，我要继续努力，不然就这个水平真去打比赛就要变成大笨猪了。
（事后看来虽然还是实际上让商品按价格排序了，但其实直接遍历一遍也没问题，但是重要的还是利用这个顺序，至于找这个顺序的方式其实无所谓）
2025年10月6日