NOIP 2017系列解题报告 – [题组/NOIP]


Day2 T2 宝藏 状态压缩动态规划

你可以点击这个链接下载全部的AC代码

题目传送门 (LOJ)

题解

首先看数据范围来枚举复杂度,再通过复杂度猜想算法。我们可以发现这题接近二进制枚举/状压DP的数据范围,分析一下题意觉得是状压DP。

N 很小,我们可以枚举起点。

  • 设状态为 S 的情况下,最小的花费是 F(S)

我们用DFS更新状态, 对于一个状态 S 枚举其中所有的已到达的点,对于每个枚举的点,枚举其能到达的点,判断是否需要更新状态,条件即为 1. 到目标状态是否答案比之前更新的优秀 2. 枚举的点是否已经在状态里了。

这个方程很简单就能更新, 但是聪明的你发现了,这玩意虽然能 A 题,但是从复杂度到正确性都不对 。

代码包里包含的是这份错误可 A 的代码。

如果你只是想 A 了这道题,那可以用如上方法写了,下面讲一个正确的做法

我们把更新分层,并枚举每层有几个,分别有哪几个。

状态 F[dep][S] 表示现在处理到第 dep 层,状态为 S 的最小花费

预处理一个 Dis[S1][S2] 代表从 S1 \to S2 最小的花费* 此话费不包含深度,只包含权值

上面的预处理需要先预处理一个Dis[p][S] 表示 p \to S 最小的花费。

假设我们已经知道了 F[dep][i] 考虑哪些状态可由 F[dep][i] 转移

我们直接枚举 i 的补集的子集为 j ,

那么转移即为 F[dep+1][i|j] = min{F[dep+1][i|j], F[dep][i]+(dep+1)\times Dis[j][i]}

第一个做法之所以时间复杂度不对,是因为每个状态可能会被枚举多次

第一个做法之所以没有正确性,是由于状态描述不全,存在更新不到最优解的情况

而第二种 DP 解决了这两个问题。

正确解法代码 :

#include 
#include 
#include 
#define C (i^S)
#define ll long long
using std :: min;
const int N = 13;
const int INF = 0x3f3f3f3f;
int n, m, S, e[N][N];
int f[N][1< INF) break;
        }
        dis[j][i] = ret < INF ? ret : INF;
    }
    for(int i = 0; i < n; i ++ ) f[0][1<

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注