~ Esoteria Algorithm in Reverse Observatory

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。按位与判断上下行间,该状态在该行的地形是否合法,不断从上一行转移。