题目传送门 方法一 看完题目,觉得这是一个神奇的博弈论题目,不会做……然后,看了一眼数据范围,n,m<=10?!好像可以暴力DP啊?来算一下可能的状态数量,同一行中放棋子的点一定是最左边的若干个,令A[i]表示第i行左边的A[i]个格子里放了棋子,根据题目要求不难发现这些性质:m>=A[ …
BZOJ1096 [ZJOI2007]仓库建设

题目传送门 这是一道比较裸的动态规划斜率优化 考虑f[i]表示前i个工厂,其中第i个一定建了仓库的最小费用。 s1[i]表示i号点到n号点的距离 s2[i]表示1~i号点的所有物资运到n号点的费用,s2[i]=s2[i-1]+s1[i]*p[i] s3[i]表示1~i号点的物资数量 $$f[j]=m …

题目大意 给定一棵带边权的树,有q次询问,每次给定m个关键点,要求删掉一些边,使得根不与任何关键点连通。 题解 咳咳 只要会虚树,这就是一道裸题。 我这种蒟蒻也只会写裸题了。。。 对每次询问建一遍虚树,然后在虚树上跑DP。 代码 #include <cstdio> #include …

题目大意 不包含4或8,且至少包含3个连续数字的数为合法的手机号码。问l,r区间内合法的手机号码有几个? Solution 这题是很显然的数位DP。当然,如果直接套dp方程可能会显得麻烦,所以还是用记忆化搜索。思路直接描述有点困难,所以直接看代码和注释。 代码 #include<cstdio …