111qqz的小窝

老年咸鱼冲锋!

codeforces 570 E. Pig and Palindromes (dp)

比赛的时候想到了是dp搞…

不过dp废…..

可能更多的是心理上…

这道题并不怎么难想,但是以觉得是dp,就给了自己一种暗示…这题我搞不出来…

实际上,我把cA掉的时候应该还有一个小时十分钟左右的样子…

d题没啥思路,所以我有大概一个小时的时间可以搞e…未必就搞不出来.

 

还有因为答案很大要取模,感觉一般取模的题,要么是数学,要么是像dp这种有递推式子的.

这道题的思路是:

因为要形成回文串,我们可以从两边往中间走,保证每一步都相同.

dp[i][x1][x2] 表示路径长度为i,左上角出发到达x坐标为x1,又下角出发到达x坐标为x2,且两条路径上对应的字母都相同的方案数.

然后判断当前格子的字母是否一样,如果一样,则考虑转移.

由于从左上角出发可以往下往右,从右下角出发可以往上往左,排列组合,所以当前状态和之前的四种状态有关.

由因为这步的状态只和上以步的四种状态有关,所以路径长度那以维要滚动掉不然会MLE

dp方程为 dp[cur][x1][x2]=(dp[cur^1][x1][x2],dp[cur^1][x1-1][x2],dp[cur^1][x1][x2+1],dp[cur^1][x1-1][x2+1])%MOD;

然后注意由于(m+n) 的奇偶性,答案会有所不同.

根据奇偶性判断从两端出发是到两个相邻的格子还是到同一个格子.

初始化的话如果(1,1)和{n,m}点的字母一样那么 dp[0][1][n] 为1,否则为0.

其他点显然都为0

说点什么

您将是第一位评论人!

提醒
wpDiscuz
粤ICP备18103363