~ Esoteria Algorithm in Reverse Observatory

LGOJ P1174 | 打砖块

Portal

假设所以砖块都为 NN,无论打的顺序如何对后面的砖块都没有影响,这就是一个普通的多重背包。

NOIAC52 | 计算机

Portal

计算机将重复上述过程,直到稳定

题中改写值的操作相当于最短路中对最短路长度的更新。每个节点上的值可以看作是从 1 号点到其它点的最短路的长度,而每个边的编号可以看作是该边的权。

hzwer7629 | 小奇挖矿 2

Portal

对于 60% 的数据,可以直接写出状态转移方程:
fi=max{fi4,fi7}+aif_i=\max {f_{i-4},f_{i-7}} +a_i

然后当成普通的一维 DP 做可以拿下 60pts。

对于 100% 的数据,由于 m109m\leq 10^9 如果直接用数组记录每个点的收益显然会 MLE。

hzwer4605 | 肥得更高

Portal

解法很多,机房有巨佬强行用线段树做。

由于每次施肥都会使肥力下降,最小值可以直接贪心解决,不断对肥力最低的施肥即可。如果求最大值,由于施肥使肥力下降,所以不更新当前最优选择显然是错误的。

NOIP2010T3 | 关押罪犯

Portal

考虑这样一个问题:是否存在一种分配罪犯的方案,使冲突事件的影响力不超过 midmid 。显然,当 midmid 较小时可行的方案对于更大的 midmid 仍然可行。换言之,本题的答案具有单调性,可以通过二分法,把求最值的问题转化为判断问题。

NOIP2017D2T2 | 宝藏

Portal

观察题目,12 个顶点,1000 条边,显然有很多重边(显然是状压 DP)。所以在输入时不断取最短边,最后边数不超过 122 条。由于题目求的是一个花费最小的生成树,并不关心从以哪个点为根,显然对于一棵生成树,取不同的点为根只会有深度的差别,在输出时找出所有深度中花费最小的即可,而不必枚举根节点。因为有 12 个顶点,显然状态有一维应为状态压缩的被探索过的顶点。

NOI2001D2T1 | 炮兵阵地

Portal

炮兵的攻击范围是上下左右 2 格,那么显然应以行为阶段,以该行的放置情况和上行的情况作为状态。直接出状态转移方程:
fi,j,k=max{fi1,k,t+cj}f_{i,j,k}=\max{f_{i-1,k,t}+c_j}

SCOI2005D2T3 | 互不侵犯

Portal

按照状压 DP 套路,第一维为行,第二维为使用的国王数,状态压缩描述第 ii 行的状态。预处理出合法状态和该状态下有几个王。当第 ii 行的状态和该状态左右移再与 i1i-1 行的状态为假才转移。直接写出状态转移方程:
Fi,j,ck+cj+=Fi1,k,ckF_{i,j,c_k+c_j}+=F_{i-1,k,c_k}

POJ3254 | 玉米田

Portal Soruce

@赫鲁晓夫应该是最入门的状压 DP 题。按照状压 DP 套路,行为阶段,状态压缩去描述行的每一格种不种玉米。预处地形时,将不可用的位置或 1。按位与判断上下行间,该状态在该行的地形是否合法,不断从上一行转移。