动态规划

151017模拟 动态规划

151017模拟

今天考的题比较简单,一个半小时AK了。但是后来机房突然停电.....幸好代码早早就交了= = T1 表达式 感觉好久没做这种类型的题了,题目给的信息非常准确严谨。首先空格不能直接吃掉,而是应该当作一个正常字符来处理。然后就可以把所有连续的数所在区间设为合法区间,最后DP一下即可。 [crayon-5···
141017模拟 动态规划

141017模拟

T2 喝喝喝 思路非常好,就是先把取模的式子变形,化为a[x]-mod=k*a[y],这样可以知道,满足要求的数对就是前面的数减去mod后是后面的数的倍数的数字。那么,我们有两种思路,一是从前往后枚举,每次更新以当前点为右端点,最左能到达哪里,但是这样需要枚举当前数的倍数,如果不加优化或者分块的话时···
111017模拟 征途堆积出友情的永恒 堆优化DP 动态规划

111017模拟 征途堆积出友情的永恒 堆优化DP

感觉这套题唯一值得总结的是第三题。 首先,裸的DP方程非常好推,为了方便起见,我们把b的下标设为[0,n-1],则有: $$ f[i]=min(f[j]+max(s[i]-s[j],b[j])) ( i-k \leq j \leq i-1 ) $$ 那么,我们如果先转化掉max的限制,那么式子可以拆···
101017模拟 动态规划

101017模拟

虽然今天考试又翻车了(暴力分都没拿全),但是这套题还是非常值得总结的。 T1 小奇挖矿2 考试的时候注意到+4+7很奇怪,也试着凑了几个数,但是因为写错了没找到规律,乖乖打了暴力(然而处理重复没搞好)。实际上,如果认真把4和7能凑出来的数写出来的话,可以发现,4和7可以凑出{4,7,8,11,12,···
BZOJ4007 [JLOI2015]战争调度 DP+DFS 动态规划

BZOJ4007 [JLOI2015]战争调度 DP+DFS

考试的时候先想到的是确定了最下面一排的选择情况后,上面的点只要扫一遍就一定能确定了,之后去打了状压暴力。。。 实际上,如果反着想,如果上面的点确定后,下面的点选择情况也一定能确定,因为最下面每个点产生的贡献只与它的所有祖先节点有关。接着,如果我们已经确定了当前枚举到的一个点,并且该点上方所有祖先节点···
BZOJ3566 [SHOI2014]概率充电器 概率+树形DP 动态规划

BZOJ3566 [SHOI2014]概率充电器 概率+树形DP

对现在来说算是非常难的DP,这样计算感觉很不好想啊,但是思路其实很清晰。 首先,这题要求的其实就是每个点被充电的概率,但如果正着推会很复杂,因为充电的情况比较多,所以我们计算每个点不被充电的概率。 假设我们目前在计算点i的值,那么把树划分成三个部分:i的父节点及以上部分,i以及i的子树,i的兄弟节点···
BZOJ4000 [TJOI2015]棋盘 状压DP+矩阵乘优化 动态规划

BZOJ4000 [TJOI2015]棋盘 状压DP+矩阵乘优化

题目描述不是很清楚,实际上就是给你一个矩阵表示每个点的攻击范围,若下标均从1开始,点在第2行第p+1列,求放棋子的可行方案。 实际上是状压DP的水题,枚举行,枚举上一行状态,枚举本行状态即可,但是这题的行数开的比较大,实测普通的DP只能得70分,观察式子发现,合法的状态并不多,每行撑死也就64种,而···
Evensgn剪树枝(tree.*) 树形DP 动态规划

Evensgn剪树枝(tree.*) 树形DP

又是一道树形DP,考试打暴力期望60,然而只骗到了30。思路非常不显然,至今懵逼。设f[i][0]表示i点上方的连通块中不包含黑点,在i的子树中的方案数;f[i][1]相反。这样设计状态,可以考虑砍i点的父边。 设当前考虑的是u点,先不考虑u点的颜色,递归处理u的子树,递归完成后,再考虑f[u]的取···
BZOJ1076 奖励关 期望概率+状压DP 动态规划

BZOJ1076 奖励关 期望概率+状压DP

看数据范围,是期望+状压,状态转移也很好想,但是这道题如果正向转移会比较麻烦,因为处理无效状态转移到有效状态会比较麻烦。但是,如果逆向思考,就会容易一些。设f[i][j]表示前i次选到了状态为j的最优解。倒序枚举每一次,枚举状态,枚举该次选到的物品,若当前状态允许选择该物品,则该物品可以选或不选,由···
GDOI2014 拯救莫莉斯 状压DP 动态规划

GDOI2014 拯救莫莉斯 状压DP

注意题目是“n*m<=50”,最坏情况应该是7x7的矩阵,显然不能直接暴搜,那么只能用状压DP来做。因为当前一行的状态选择只与其上下两行有关(第一行和最后一行例外),所以设f[i][j][k]表示前i行,i-1行状态为j,i行状态为k时的最优解。枚举行数、i-1行状态、i行状态、i+1行状态,···