[DP]HDU6356(2018多校练习赛第五场)【Glad You Came】题解
题目概述给出长度为 $n$ 的数字串，求最长非降子序列的长度，允许翻转一个区间 $[l,r]$ 。解题报告因为数字串，所以我们可以利用数值定义状态来快速转移，而翻转考虑三段DP：$f[i][j]...
[DP+线段树维护矩阵转移]Codeforces573D【Bear and Cavalry】题解
题目概述给出 $\{a_n\}$ 和 $\{b_n\}$ 以及刚开始 $P_i=i$ 的排列 $\{P_n\}$ ，有 $m$ 个询问，每次询问先交换 $P_x,P_y$ ，然后询问 $max\...
[DP]BZOJ2424(HAOI2010)【订货】题解
题目概述在第 $i$ 个月月初需要提供 $w_i$ 的货物，购买货物的单位价格为 $p_i$ 。货物可以存在上限为 $S$ 的仓库，但每月月底需要支付的单位价格为 $m$ ，仓库刚开始为空最后也...
[DP]BZOJ1190(HNOI2007)【梦幻岛宝珠】题解
题目概述有 $n$ 个物品，每个物品的体积满足 $a\cdot 2^b$ ，背包体积为 $W$ ，求最大价值。解题报告直接上背包！因为每个物品体积满足 $a\cdot 2^b$ ，所以我们可以定...
[LIS]洛谷3365【改造二叉树】题解
题目概述给出一棵 $n$ 个节点的二叉树，现在可以修改任意个节点的权值（只能改成整数），问至少多少次能把这棵二叉树改成BST。解题报告先中序遍历得到序列，然后就是用最少的次数把这个序列改成上升的...
[裴蜀定理+DP]LOJ2523(HAOI2018)【奇怪的背包】题解
题目概述给你 $n$ 种物品，每种物品有无数个，体积为 $V_i$ ，选出若干种物品使得这些物品存在一种方案使得体积加起来 $mod\ p=w$ ，问方案数。解题报告怎么我一道HAOI题都不会啊...
[DP+组合]LOJ2538(PKUWC 2018)【Slay the Spire】题解
题目概述有 $n$ 张攻击牌（造成攻击牌数值的伤害）和 $n$ 张强化牌（攻击牌伤害均 $\times$ 强化牌数值），从中抽出 $m$ 张并选出最优秀的 $K$ 张打出，求所有方案造成的伤害之...
[拓扑+DP]LOJ2060(HAOI2016)【食物链】题解
题目概述给出 $n$ 个生物 $m$ 条能量流动，求食物链个数。解题报告脑子不好用了，划波水。生物题了解一下。食物链的开始通常是绿色植物（生产者）,从绿色植物开始至少要有三个营养级。书写食物链是...
[DP]UOJ300(CTSC2017)【吉夫特】题解
题目概述求不上升OrzJZ子序列的个数，OrzJZ子序列需要满足 $\prod_{i=2}^{k}{a_{i-1}\choose a_i}\ mod\ 2=1$ 。解题报告因为一个 $0$ 都不...
[DP]BZOJ1566(NOI2009)【管道取珠】题解
题目概述有两个管道，第一个有 $n$ 个黑白珠子，第二个有 $m$ 个黑白珠子，每次可以从一个管道取出最靠管道口的珠子。假设有 $k$ 中取珠子的方法，第 $i$ 种方案的方案数为 $a_i$ ...
