zcmimi's blog

arrow_back动态规划共96篇文章

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

点击跳转

先考虑每种硬币可以用无数次

f_i表示金额为i有多少种方案

f_i = \sum_{j=1}^4 f_{i-c[j](i \ge c_j)}

我们再来考虑硬币使用次数有限制怎么办

不合法的情况有:

1超额

1,2超额

1,3超额

1,4超额

1,2,3超额

1,2,4超额

1,3,4超额

1,2,3,4超额

...

要注意的是在多种硬币限制的情况下可能会减去多次,或加上多次

比如1超额,2超额,(1,2同时超额被减去两次,这是就要加回来

(1,2,3)(1,2,4)又是多算的...

是不是更直观的了解了容斥?

为了方便,我们可以枚举二进制下状态来更加优美实现。

(当有奇数种不合法的时候减去,偶数种不合法时加上)

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
查看原题

点击跳转

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

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

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

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

点击跳转

斜率优化入门题

f_i表示前i件玩具的制作费用

f_i=\min_{j=1}^{i-1}(f[j]+(i-j-1+s_i-s_j-L)^2)

显然\Theta(n^2)不能满足要求

a_i=s_i+i,b[i]=s_i+i+L+1

(都只与i有关)

那么 f_i=\min_{j=1}^{i-1}(f_j+(a_i-b_j)^2) \\\text{展开得}\\ f_i=f_j+{a_i}^2-2a_ib_j+{b_j}^2 \\\text{移项得}\\ 2a_ib_j+f_i-{a_i}^2=f_j+{b_j}^2

x=b_j,y=f_j+{b_j}^2 y=2a_ix+(f_i-{a_i}^2)

可以看成一条斜率为2a_i的直线

f_i含义转化为当上述直线经过点(x,y)(b_j,f_j+{b_j}^2)时,直线在y轴的截距上加上{a_i}^2

题目就是要找这个最小的截距

我们可以将这条直线从下往上平移,直到经过第一个点

这样的话我们可以维护一个下凸壳

求的过程大概是这样:

https://www.desmos.com/calculator/mqsdvzuaee

那么如何维护这样一个下凸壳呢?

可以发现凸壳中的相邻两点的斜率是递增的

我们可以用单调队列维护

那么查询呢?

我们可以发现:

如果当前直线经过的点左边的斜率<当前斜率<右边的斜率,

那么这个点就是最优的。

我们可以按照下面的方案实现:

设队头为h,队尾为t,队列数组为q,s(i,j)为直线ij的斜率

  1. while(s(q_h,q_{h+1})<2a_i)++h;
  2. 当前队头的点最优,用这个点计算出f_i
  3. while(s(q_{t-1},q_t)>s(q_{t-1},i))--t;
  4. 队尾插入点i

对于3操作的解释:

假设当前插入的是红点,那么绿点明显在凸包内,要删除掉

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

点击跳转

Easy top: 0

Solution:   期望题总是贼有意思。

  本题期望comboo的期望连续长度的平方,所以我们设f_i表示到了第i位的总期望combo,g_i表示到了第i位结尾的连续o的期望长度,那么分情况讨论:

  1. s_i == o
  2. s_i == x
  3. s_i ==\ ?
avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

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

点击跳转

f_{k,i}:第i位,改变k

显然f_{k,i} = MIN(f_{k-1,j}+res(i,j))

那这个res要怎么求呢?

res=MAX(a_i,..,a_j)-\sum_{t=j-1}^i a_t

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

点击跳转

二分最大值,然后树型dp

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

点击跳转

树形dp up and down

考虑 up:

s_x为点x子树中所有点到x的距离之和

S_x = \sum (s_{to}+siz_{to})

考虑 down:

s_{to} = s_{to} + (s_x-s_{to}-siz_{to}) + n - siz_{to}

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

点击跳转

f[i][j]表示第i天有j只股票最多赚多少钱 \\

  1. 直接买 f[i][j] = -ap[i] \times j
  2. 不买不卖

    f[i][j] =f[i-1][j]

  3. 买股

    f[i][j] = f[i-w-1][k] - ap[i] \times (j-k) (j-as[i] \le k \le j)

  4. 卖股

    f[i][j] = f[i-w-1][k] + bp[i] \times (k-j) (j \le k \le j + bs[i])

但是这样还是O(n^3)的复杂度,得想办法降到O(n^2)

看一下f[i][j] = f[i-w-1][k] - ap[i] \times (j-k) (j-as[i] \le k \le j)

可以化为f[i][j] = (f[i-w-1][k] + ap[i] \times k) - ap[i] \times j (j-as[i] \le k \le j)

于是就可以单调队列了 OωO

6/10
Search
search