主页
搜索
最近更新
数据统计
赞助我们
系统公告
1
/
1
请查看完所有公告
题解：P10027 梦境世界
最后更新于 2025-06-16 08:14:41
作者
Epi4any
分类
题解
题解
P10027
复制 Markdown
查看原文
更新内容
很巧妙的一道题，做法是 dp 套 dp，why？ 很容易可以想到这样的状态设计，```f[i][j][p]```代表走到格子 $(i,j)$，并且已经后退了 $p$ 步。 直接前进很好说： ``` f[i][j][p]=f[i-1][j][p]+f[i][j-1][p] ``` 同样的做法可以构造出来后退的转移方程： ``` f[i][j][p]=f[i+1][j][k+1]+f[i][j+1][k+1] ``` **但是**，这样做是错的，因为这道题有倒退这个操作，然而这一步会导致一个格子经过多变，只做一次 dp 的话就会破坏最优子结构性质，但是可以发现多次经过一个点永远可以简化成若干个“一个方向走出去绕一圈”的行为，于是想到再加一个 dp（其实没见过一点也不好想到），```g[i][j][p]``` 代表从 $(i,j)$ 出发，倒退了 $p$ 次有多少种走法可以再绕回 $(i,j)$。 转移方程是： ``` g[i][j][p]=(g[i+1][j][p]+a[i][j+1][p])*g[i][j][k-p-1] ``` 此时后退的总做法就是： ``` g[i][j][k-p] ``` 于是得出 $f$ 的转移方程： ``` f[i][j][p]=(f[i-1][j][p]+f[i][j-1][p])*g[i][j][k-p] ``` 最终答案为 $max(f[i][j][p])$，$p \in [1,n]$。
正在渲染内容...
点赞
0
收藏
0
