zcmimi's blog

arrow_back动态规划共96篇文章

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

f[i][j]表示前i个分j个邮局

f[i][j]=\min(f[x][j-1]+w[x+1][i])

满足决策单调性

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

f_i表示以i开头合法子序列方案数

f_i=\sum_{j=i+a_i+1}^{n+1} f_j \times {j-i+1 \choose a_i}

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

f_i表示只经过第i个黑点的方案数

f_i最初为{x_i+y_i-2}\choose {x_i-1}

减去(1,1)(x_i,y_i)这个范围内所有f_j的方案数就是最终答案了

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

点击跳转

可以看到n\le 15,我们很容易想到状压

状压解法:

f[i][j]表示到了第i位,匹配的状态为j

代码:

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

点击跳转

可以理解成从左上角到右下角的最长路(每层只能取一个)

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

点击跳转

E_xxn的期望时间

E_x = \sum_i E_i \times p_{xi}\prod_{j=1}^{i-1}(1-p_{xj})

我们可以用类似dij的思想来更新

每次取出E_x最小的x来更新

要注意我们现在求出来的还没算上1需要先停留在原地的概率,

除掉一个1-\prod p才是最终的期望

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

点击跳转

f_{i,j,k,(1/0)}a_i(选或不选),b_j,k

f_{i,j,k,0} = f_{i-1,j,k,0} + f_{i-1,j,k,1}

a_i = b_j:

f_{i,j,k,1}=f_{i-1,j-1,k,1}+f_{i-1,j-1,k-1,0}+f_{i-1,j-1,k-1,1}

a_i = b_j:

f_{i,j,k,1} = 0

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

点击跳转

题目大意:

给定一个长度为 n\leq 500000 的序列 a_1, a_2, \cdots, a_n ,要求对于每一个 1 \leq r \leq n ,找到最小的非负整数 f_{r} 满足

\forall l\in\left[1,n\right]:a_l \leq a_r + f_{r} - \sqrt{|r-l|}

解法

考虑l<r,r>l的将序列翻转后再来一次就可以了

f_r= \max(a_l+\sqrt{r-l})-a_r(l\in[1,r])

可以证明f_r的最优决策点是递增的

可以打表

分治解法

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

点击跳转

dp

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

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

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

点击跳转

先把连续的块缩成一个点

f[i][j]表示[i,j]全部涂成一种颜色最少要多少次

f[i][j] = \min(f[i+1][j],f[i][j-1])+1

c[i]==c[j],f[i][j]=f[i+1][j-1]+1

4/10
Search
search