zcmimi's blog

arrow_back动态规划共96篇文章

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

点击跳转

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

点击跳转

f[i][k]为第i位,分成k

f[i][k] = MAX(f[j][k-1] + cnt[j+1][i])

这样的话肯定复杂度爆炸

既然看到MAX,那是不是可以用线段树优化呢?

记录每个点贡献的范围,更新时把这个范围的点++就可以了。

相信看代码可以看懂

其实我还加了滚动数组OwO

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

点击跳转

f(i,j)表示前i个划分成j段最少的费用

我们设calc(l,r)表示[l,r]划分成一段的费用

f(i,j)=\min_{x=1}^i(f(x-1,j-1)+calc(x,i))

可以发现这个dp方程具有决策单调性

i<i',那么k_i\le k_{i'}(决策点)

把连续一段拆成两边更优x^2+y^2\le (x+y)^2(x,y\ge 0)

更巧的是w(l,r)可以用类似莫队的方法线性转移

这里采用分治的方法实现

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的,然后往后面枚举就可以了,因为不关怎么样我们都要把全部取完,先取后取是一样的

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

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

点击跳转

这篇题解可能是对楼下的补充

我们考虑每个点能贡献多少次

无标题.png

设当前节点为x,路径有三种情况,上图分别对应情况1,情况2,情况3

  1. x子树内\rightarrow x \rightarrow x子树外(包括x)

  2. x子树内(包括x)\rightarrow x \rightarrow x子树内

  3. x子树外\rightarrow x \rightarrow x子树内

我们可以先处理出与x的距离为偶数和与x的距离为奇数的点的个数,分别记作f_x,g_x

那么f_x = 1 + \sum g_{to},g_x = 1 + \sum f_{to}(tox的孩子)

我们来考虑所有情况

  1. ans += V_x \times (f_x-g_x) \times (n-siz_x+1)(可以在x的子树中随机选一个往子树外面走(可以指走到x))

  2. ans += V_x \times (g_{to}-f_{to}) \times (siz_x-siz_{to}-1)

    ans+= V_x \times (siz_x-1)(可以从x直接向下走)

  3. 我们需要记录x子树外与x的距离为偶数和与x的距离为奇数的点的个数,分别记作uf_x,ug_x

    我们可以通过bfs从上到下来处理,那么

    uf_x=ug_{fa_x}+g_{fa_x}-f_x

    ug_x=uf_{fa_x}+f_{fa_x}-g_x

    ans += V_x \times (uf_x-ug_x) \times siz_x

接下来放代码:

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的最优决策点是递增的

可以打表

分治解法

10/10
Search
search