shyyhs

DP专题

图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38) 题解(330)

/ 注册

全部文章 / DP专题（共52篇）

B - Adjacent Chmax

第一次自己写出700700700分的题!!! 记录一下. 首先能到iii位置后面的一定是满足iii后面的连续的maxmaxmax.这点很显然. 那么我们设置dpdpdp状态: fi,jf_{i,j}fi,j为到了第iii个位置,值是jjj的方案数.注意这是从111开始数到iii考虑本质不同的序列....

单调栈 dp

2022-08-16

1 741

1426

大概这才是期望dpdpdp的入门题吧. 可以合并当前项的dpdpdp哦！首先定义方程fif_ifi表示已经拿到了iii个,还需要拿多少次能全部拿完的期望. 那么容易得到转移方程: fi=fi∗(i/n)+fi+1∗(1−i/n)+1f_i=f_i*(i/n)+f_{i+1}*(1-i/n)+1f...

期望dp

2022-08-10

0 507

斜率优化dp

是一种可以针对i j具有某种单调性来用斜率优化dp{dp}dp转移的一种方式. 例:BZOJ1010 玩具装箱toy 很容易的写出dpdpdp方程,令fif_ifi表示解决前iii个的最小花费. 那么转移也很明显就是:fi=fj+(sumi−sumj−L+i−j−1)2f_i=f_j+(sum_i...

斜率优化dp

2022-08-09

0 511

干草堆tower

一个很好的dp. 显然最优的方案一定是最瘦的情况,从前往后是没有转移性质的,也不符合dp的最优解转移. 那么考虑从后往前转移,定义: fif_ifi表示到了第iii个的{最小宽度是多少,高度是多少},因为到了iii最小宽度的情况下,高度是最高的,顺带记录下高度即可. 转移很显然： fi.first...

单调队列优化dp

2022-08-07

0 477

D - Deterministic Placing

一个很难的题目写个博客加深印象. 首先可以把树划分成许多链每个链可以分为0端和1端有三个结论(可证). 1.0端和0端不能在一起 2.1端和1端不能在一起 3.中间点不能和别的端点在一起除此之外其他都是合法的. so,把链划分dp转移可以得到答案. 定义dp状态: 0:表示为中间点端点两个...

树形dp

2022-07-19

0 580

Recovering BST 来自专栏

感觉很妙,所以来水题解了~ 问给你一个升序序列,问是不是可以还原一个bstbstbst,使得相邻的两个节点gcdgcdgcd不为111.n<=700n<=700n<=700. 因为是颗二叉树,很容易想到区间dpdpdp,然后假设区间[l,k][l,k][l,k]满足了,这个区间的父...

dp

2022-05-03

1 425

XOR Partitioning 来自专栏

这题也好难诶!!!好叭可能只是对于我.因为dp方程不是我写的,网上也没注释.. 首先满足子区间异或和相等且当形式为 A 0 A 0 A 0..这种形式的异或前缀和才行. so?这题就做完了,我们进行dp即可. 令dp为现在出现位子i值为A的区间的种数,很明显,当前出现假如为A,那么它可以和前面的一起...

dp

2022-04-22

0 413

数位dp 来自专栏

dp

2021-06-03

2 692

值得学习(too lazy~) 来自专栏

这才是真正的博客吧~

dp

2021-03-25

1 667

贝壳找房2021届校招算法卷3[编程题]世界杯来自专栏

直接dp即可. #include <bits/stdc++.h> using namespace std; const int N=2e3,M=12; double f[N][M];//第i个人在第j轮生出的概率. double F[N][N];//第i名战胜第j名的概率. int ...

dp

2021-01-27

3 782