zcmimi's blog

arrow_back记忆化搜索共3篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

dp

(其实记忆化搜索也可以啦)

只要假设组成n的数是递增或递减,就不会重复了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

我们可以把每一行的SG异或

每一行只有20个,所以可以用状态压缩

可以通过动态规划或记忆化搜索的方式处理出每种状态的SG

avatar
zcmimi
2019-01-21 18:36:18

LG 3953 逛公园

题意: 求dis(1,n)<=MinDis(1,n)+K的路径数

用拓扑啊什么的一想就很麻烦。

有一种玄学的做法:记忆化搜索

f[x][k]表示dis(x,n)<=MinDis(x,n)+k的路径数。

先跑一般反向的最短路,然后dfs

考虑边(x,y,w),

\because Mindis[x]-Mindis[y]+w<k

\therefore f[x][k]+=f[y][k-(Mindis[x]-Mindis[y]+w)]

\therefore f[x][k] = \sum f[y][k-(Mindis[x]-Mindis[y]+w)]

1/1
Search
search