zcmimi's blog

arrow_back状压dp共15篇文章

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

点击跳转

看了看数据范围,可以知道是状态压缩+区间dp

我们设f[i][j][t]表示[i,j]合并后状态为t获得的分数

f[i][j][t] = f[i][k][t'] + f[k+1][j][t''] (t'|t'' = t)

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

点击跳转

f[st][sta]表示起点是st,当前节点是否访问过的状态二进制下是sta

顺便记录d[st][sta]表示f[st][sta]最小时每个节点距离st的距离

我们可以用填表法向前推进

f[st][sta'] = \min(f[st][sta'],f[st][sta]+(d[st][sta][x]+1)\times L) (sta' = sta | 2^{to-1})

最坏情况下复杂度: \Theta(n \times 2^n \times n^2)

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

点击跳转

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

点击跳转

f[i][j]表示状态为i,上一个吃的是第j道菜

f[i'][k]=\max(f[i'][k],f[i][j]+a[j]+d[j][k]) (d[j][k]表示连续吃j,k能额外获得多少满意度)

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

点击跳转

f[x]表示状态为x时最少走多少步

枚举现在取哪两个点,然后

f[x|2^{i-1}|2^{j-1}]=\min(f[x|2^{i-1}|2^{j-1}],f[x])

如果直接枚举不剪枝的话可能会TLE

所以我们只要找到第一位是1的,然后往后面枚举就可以了,因为不关怎么样我们都要把全部取完,先取后取是一样的

(如果不懂可以自己模拟一下)

2/2
Search
search