题意有一个长为 $n(\le 10000)$ ，高为 $m(\le 1000)$ 的游戏场景。玩Flappy Bird，在位置 $i$ 点一下会上升 $x_i$ ，否则会下降 $y_i$ ，手速极快每秒可以点多下。有 $k$ 个位置有管道，其中空隙的范围为 $[L_i,H_i]$ 。可以从位置 $0$ 的任意高度出发，问至少要点几次才能到位置 $n$ ？如果无法到达，最多能跨过多少个管道？题...
题意有一棵 $n(\le 100004)$ 个点的树，从根节点出发。节点 $x$ 能放梅花，仅当其所有子节点 $y$ 上都放了 $w_y$ 朵梅花。对于 $\forall i\in [1,n]$ ，如果要在 $i$ 上放 $w_i$ 朵梅花，则至少需要在过程中准备多少梅花？题解可以发现对于节点 $x$ ，一定是按某种顺序遍历所有子节点 $y$ 放上梅花，而且不同的顺序得到的答案也不相同。考虑...
Codeforces Round #572 (Div. 2) 题解题意给出一个长度为 $n(\le 1000)$ 的序列和 $k$ ，求所有长度为 $k$ 的子序列中美丽值之和。美丽值定义为序列中的数两两之间差值的最小值。题解利用差分的思想。令 $g(x)$ 为美丽值 $\geq x$ 的子序列个数，那么答案就是 $\sum_{i=1}^\infty g(i)$ 。先把序列从小到大排序，这样...
题意有 $n(\le 50)$ 个人用 $m(\le 50)$ 张卡牌玩游戏。第一局由玩家 $1$ 坐庄抽卡，如果卡上的数字是 $x$ ，那么从他的位置数第 $x$ 的人就被处决。第二局就由被处决的人的后一个人坐庄，以此类推，最后剩下的玩家获得胜利。求每个玩家的胜率。题解概率DP，用 $f[i][j]$ 表示还剩 $i$ 个人，从坐庄的人往后数第 $j$ 个人的胜率。如果只剩 $1$ 个人，...
题意有一个长为 $n(\le 256)$ 的数组 $a$ ，第 $i$ 个数有权值 $b_i$ 。从中选取 $K$ 个点 $c_j$ ，把 $a$ 上的数都移过去，代价为 $\sum (a_i-c_j)^2\times b_i$ 。求最小代价。题解非常暴力的DP。用 $f[i][j]$ 表示前 $i$ 个数选了 $j$ 个点，其中第 $i$ 个点选的最小代价。预处理选取 $i,j$ 后 $(...
题意有 $n(\le 18)$ 只绿猪，位置在 $(x_i,y_i)$ 。每次可以从 $(0,0)$ 发射一只小鸟，开口向下的抛物线上的猪会被消灭。问至少要发射多少只小鸟。题解容易想到暴力的状压。用 $f(S)$ 表示消灭集合 $S$ 中的绿猪需要多少只小鸟，预处理出经过 $i,j$ 两只猪的抛物线可以消灭的猪 $s[i][j]$，枚举不在 $S$ 中的两只猪 $i,j$ ，方程式为：$$\...
DarkBzoj提交地址题意有 $N(\le 2000)$ 个农民, 他们住在 $N$ 个不同的村子里. 这 $N$ 个村子形成一棵树。每个农民初始时获得 $X$ 的钱。每一次操作, 一个农民可以从它自己的钱中, 取出任意数量的钱, 交给某个相邻村子的农民。对于每个农民给定一个值 $v_i$, 求：最少需要多少次操作, 使得每个农民最终拿到的钱 $\geq$ 给定的值。题解有个结论：每条边最...
DarkBzoj提交地址：因为没有SPJ，所以需要特殊处理答案如下：if (ans) printf("%.10f",ans);
else puts("0");题意某个公司有 $n(\le 5\times 10^5)$ 个人, 上下级关系构成了一个有根树，其中有个人是叛徒(这个人不知道是谁)。对于一个人, 如果他下属(直接或者间接, 不包括他自己)中叛徒...
题意给一个数字串 $s(|s|\le 10)$ 和正整数 $d(\le 1000)$ , 统计 $s$ 有多少种不同的排列能被 $d$ 整除（可以有前导 $0$）。题解$|s|$ 较小，考虑状压。用 $f(S,i)$ 表示下标集合 $S$ 内的数都用过了，当前数 $\equiv i\pmod d$ 。每次枚举一个不在 $S$ 的数 $j$ 加入转移，方程式为：$$f(S,i)\rightar...
题意给一个 $n(\le 15)$ 个点 $m$ 条边的无向连通图（不存在自环或重边），每条边有一个边权，要求割掉若干条边，使 $1$ 到 $n$ 只有 $1$ 条路径（不经过重复点），问割掉的边权和最小是多少。题解可以发现最后图的形态一定是一条链，链上可能挂了若干个连通块，要最大化图的边权和。$n$ 比较小，考虑状压。用 $f(S,i)$ 表示目前链上的终点为 $i$ ，加入的点集为 $S...
题意有 $n(n\le 2\times 10^5)$ 头奶牛，有 $m(m\le 10^5)$ 组关系 $(l,r)$ ，表示 $[l,r]$ 奶牛中有且仅有一头有斑点。问最多有多少头奶牛有斑点。题解第一反应就是差分约束，不过因为是从DP点进来的所以我去看题解确认了下，得知会T（除了玄学的限定次数）。方程式还好想，就是转移比较神奇。用 $f[i]$ 表示第 $i$ 头牛有斑点的前提下前 $i...
题意在 $n(n\le 100)\times m(m\le 2)$ 的矩阵中选出 $k(k\le 10)$ 个子矩阵，使得这些子矩阵中数字和最大。子矩阵之间不能重叠。题解如果做过 CF1199F 就很容易做出来。用 $f[l][r][x][y][k]$ 表示在左下角为 $(l,x)$ ，右上角为 $(r,y)$ 的区域中选 $k$ 个子矩阵的最大和。枚举横纵的中间点，以及两部分选取的子矩阵的...
题意长度为 $N$ 的小写字母串，要求增加或删除字母使其变成回文串。每个字符的增加和删除有固定的花费，求花费的最小值。$N\le 2000$ 。题解区间DP，用 $[i][j]$ 表示将 $[i,j]$ 变成回文串的最小花费。如果 $S_i=S_j$ ，那么可以直接从 $f[i+1][j-1]$ 转移过来。对于上一个状态 $[i+1,j]$ ，可以删掉 $S_i$ ，也可以在右边添加一个 $...
题意有 $N$ 头奶牛，每头奶牛都有智商和情商，要从中选出一些奶牛参会，要求情商总和 和 智商总和 都不能 $< 0$ 。问情商和智商总和最大是多少。$N\le 400$ ，智商情商 $\le 1000$ 。题解可以把智商当作体积，情商当作价值来做背包，最后答案即为 $\max i+f[i]$ 。因为有负数所以要偏移一下，同时如果当前体积为负数要正序枚举。#include<bit...
双倍经验：洛谷2734 游戏 A Game （还不用滚动数组）题意有 $N$ 个数，两个人轮流取，每次可以取左右两端的数。两个人都绝顶聪明，问第一个人最多能取到多少。$N\le 5000$ 。空间限制 $64M$ 。题解用 $f[i][j]$ 表示在 $[i,j]$ 最多能取到多少，用 $sum[i][j]$ 表示 $[i,j]$ 的和。因为两个人都会取最优方案，所以方程式为：$$f[i][...