NOI2020

赛前才发现真题基本没做过/kk

Day 1

美食家

老经典题了，先写出一个 dp，\(f[i,j]\) 代表第 \(i\) 天在 \(j\) 号点的最大权值。转移显然，由于 \(w\le 5\) 所以只需保留前 \(5\) 天的值。于是可以构造一个 \(5n\times 5n\) 的矩阵。显然转移这是一个广义矩阵乘法。倍增预处理然后向量\(\times\)矩阵。复杂度 \(O((5n)^3\log T+(5n)^2k\log T)\)。