Day48【NOIP模拟赛13】

序列

很好的一道 “送命题” “签到题”，想了两个小时一分没有，破防了。

考场上想到了定义 $d{p}_{i,j,0/1}$ 表示处理完前 $i$ 个数，当前数为 $j$，是否被修改的方案数，然而不会去重，遂开摆。

所以为了 不重不漏 的统计方案数，我们增加一种状态 $d{p}_{i,j,2}$ 表示当前位既有可能被修改，又有可能未被修改的方案数，请注意这种状态与其它两种状态并不存在所谓的包含关系，一定的情况就只能属于 $0,1$，可能的情况就只能属于 $2$。

当然为了方便些，下文中 $d{p}_{i,j,0/1/2}$，分别表示表示处理完前 $i$ 个数，当前位为 $j$，未被修改($0$)，都有可能($1$)，一定被修改($2$)的方案数。

现在考虑转移：

• $m$ 后面可以接任意数，$1$ 可以接在任意数后面。
• 如果上一位是一个被修改的不为 $m$ 的数，当前位一定被修改。
• 如果上一位未被修改，那么这一位要么不被修改，要么被修改为 $1$。
• 如果上一位被修改成了不是 $m$ 的数 $x$，当前位要么为 $1$，要么为 $x+1$。
• 如果当前位为 $0$，上一位要么未被修改，要么被修改为了 $m$。

把文字语言转化成状态转移方程式可得：

• $d{p}_{i,a_i,0}\leftarrow d{p}_{i,a_i,0}+d{p}_{i-1,j,0},j\in [0,m]$。
• $d{p}_{i,1,1+(a_i\ne 1)}\leftarrow d{p}_{i,1,1+(a_i\ne 1)}+d{p}_{i-1,j,0}，j\in [0,m]$。
• $d{p}_{i,1,2}\leftarrow d{p}_{i,1,2}+d{p}_{i-1,j,2},j\in [0,m-1]$。
• $d{p}_{i,j,1+(a_i\ne j)}\leftarrow d{p}_{i,j,1+(a_i\ne j)}+d{p}_{i-1,m,1}+d{p}_{i-1,m,2},j\in [2,m]$。
• $d{p}_{i,j+1,2}\leftarrow d{p}_{i,j+1,2}+d{p}_{i-1,j,2},j\in [0,m-1]$。
• $d{p}_{i,j+1,1+(a_i\ne j+1)}\leftarrow d{p}_{i,j+1,1+(a_i\ne j+1)}+d{p}_{i-1,j,1},j\in [0,m-1]$。
• 由于 $d{p}_{i-1,m,0}$ 和 $d{p}_{i-1,m,2}$ 都没有后效性，即不会影响 $[i,n]$ 这段数，所以转移前让 $d{p}_{i-1,m,0}\leftarrow d{p}_{i-1,m,0}+d{p}_{i-1,m,2}$ 没有什么实际意义，单纯方便一点。

初始状态显然有：$d{p}_{1,a_1,0}=d{p}_{1,1,(1+a_1\ne 1)}=1$。
答案显然是 $d{p}_{n,a_n,0}+d{p}_{n,m,2}$。

具体实现上，使用滚动数组，其次，这道题有点卡常，所以尽量减少取模次数就行了。

贪吃蛇

真正意义上的签到题，然而少打了个记忆化挂了 $20pts$。

考虑单独处理每一个 $(i,j)$，用类似于 $bfs$ 方式扩展当前能走到的区域，用优先队列存储未被暂时不能吃掉的点，然后乱搞，当然有两个剪枝：

• 当前权值大于矩阵最大权值，显然合法。
• 走到了一个已经处理过的合法格子，显然当前 $(i,j)$ 也跟着合法了。

最坏时间复杂度：$O(n^2{m}^2\log nm)$，然而跑的飞快，我最慢的点只跑了 $200ms$，比 std 快了十倍。 （雾

蛋糕

神仙题，当然仅指 zdj 学长的做法，std 做法啥也不是。

首先看到这道题，很自然得到一个朴素 $O(nV)$ 的 $dp$。
$d{p}_{i,j}$ 表示将 $[1,i]$ 全部变为 $0$，且使用了 $j$ 次横切操作的最小代价。
然后有转移 $d{p}_{i,j}=\min (d{p}_{i-1,j}+\max (a_i-j,0),d{p}_{i,j-1}+su{f}_{i+1})$，其中 $suf$ 表示后缀最大值。

原文地址：https://blog.csdn.net/cqbzliuhongyi/article/details/142796209

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！