标签：11 le sum times 据点 ch Day dp

Day 11

全真模拟赛

T1

赛时切了/se

首先可以直接按照a排序，一定选择一个区间

前缀和可求区间和，区间 \(l, r\) 的价值就是

\(preb_r - preb_{l - 1} - (a_r - a_l)\)

然后固定 \(r\) ，预处理出每个位置 $l 所对应的最值即可

#include<bits/stdc++.h>
#define ll __int128
#define ull unsigned long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
struct node
{
    ll a, b;
}p[500005];
bool cmp(node x, node y)
{
    return x.a < y.a;
}
ll Qb[500005], Qa[500005], mia[500005];
int main()
{
    int n = read();
    for(int i = 1; i <= n; ++ i)p[i] = {read(), read()};
    sort(p + 1, p + n + 1, cmp);
    for(int i = 1; i <= n; ++ i)Qb[i] = Qb[i  - 1] + p[i].b, Qa[i] = Qa[i - 1] + p[i].a;
    ll res = -1;
    for(int i = 1; i <= n; ++ i)mia[i] = max(mia[i - 1], Qa[i] - Qb[i - 1] - Qa[i - 1]);
    for(int i = 1; i <= n; ++ i)res = max(res, Qb[i] - Qa[i] + Qa[i - 1] + mia[i]);
    print(res);
    return 0;
}

T2

白兰。

dp

令 \(dp_{i, j}\) 表示长度为 \(i\) 有 \(j\) 个顶的排列个数

考虑往长度为 \(i\) 的排列里插入 $i + 1 若插在原本顶的旁边，则顶个数不变，否则个数增加 \(1\)

\(dp_{i,j} = dp_{i - 1, j} \times (2 * j + 2) + dp_{i - 1, j - 1} \times (2 - 2 \times j)\)

啊啊啊没想出来。

排列dp做的少了

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
const int mod = 1e9  + 7;
ll dp[5005][5005];
int main()
{
    int n = read(), k = read();
    dp[2][0] = 2;
    for(int i = 3; i <= n; ++ i)
    {
        for(int j = 0; j <= k; ++ j)
        {
            dp[i][j] = dp[i - 1][j] * (2 *j + 2) + dp[i - 1][j - 1] * (i - 2 * j);
            dp[i][j] %= mod;
        }
    }
    cout << dp[n][k] << '\n';
    return 0;
}

T3

将点按 \(x\) 排序。

设 \(dp_{i,0/1}\)表示表示以第i个点为顶端接下来向左/向右的折线方案数。

考虑依次加入 \((x_1, y_1),(x_2, y-2), . . . , (x_n , y_n)\) 然后更新dp 数组.

由于新点横坐标最大,所以只可能在折线的第一位或第二位。

转移的时候可以倒序枚举 \(j\):

• \(y_i> y_j : dp_{i,0} \gets dp_{i,0} + dp_{j,1}\)
• \(y_i≤ y_j : dp_{j,1} \gets dp_{j,1}+ dp_{i,0}\)

这样就能做到时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n)\) 了。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
const int maxn = 6005, mod = 1e9 + 7;
struct node
{
    ll x, y;
}a[maxn];
bool cmp(node a, node b)
{
    return a.x < b.x;
}
ll dp[maxn][2], n, ans;
int main()
{
    int n = read(); 
    for(int i = 1; i <= n; ++ i)
    {
        a[i] = {read(), read()};
    }
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1; i <= n; ++ i)dp[i][0] = dp[i][1] = 1;
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = i - 1; j >= 1; -- j)
        {
            if(a[i].y >= a[j].y)dp[i][0] = (dp[i][0] + dp[j][1]) % mod;
            else dp[j][1] = (dp[j][1] + dp[i][0]) % mod;
        }
    }
    ll res  = 0;
    for(int i = 1; i <= n; ++ i)ans = (ans + dp[i][0] + dp[i][1]) % mod;
    cout << (ans - n + mod) % mod;
    return 0;
}

T4

如有 \(a_i < a_j(i < j)\) 存在 \(k\) 满足 \(i < k < j, a_k > a_i\) 显然 \(a_k, a_j\) 作为前两个更优。

那么有用的前两个的对就只剩下了 \(O(n)\) 个，具体为每个数和他左边第一个比他大的数形成的对，以及每个数和他右边第一个大于等于它所形成的数对。

接着对于每个询问，按左端点从大到小排序，在求解的同时加入有用的对。

现在问题成了， 有 \(n\) 个标记 \(c_{1...n}\) 一开始全为 \(0\) ，每次操作对 \(c\) 的一个后缀取 \(max\), 或者查询一个区间 \(c_i + a_i\) 的最大值。

线段树维护即可。

真题选讲

22 Csp-S 星战

不可以，总司令！

在这一轮的星际战争中，我方在宇宙中建立了 \(n\) 个据点，以 \(m\) 个单向虫洞连接。我们把终点为据点 \(u\) 的所有虫洞归为据点 \(u\) 的虫洞。

战火纷飞之中这些虫洞很难长久存在，敌人的打击随时可能到来。这些打击中的有效打击可以分为两类：

1. 敌人会摧毁某个虫洞，这会使它连接的两个据点无法再通过这个虫洞直接到达，但这样的打击无法摧毁它连接的两个据点。
2. 敌人会摧毁某个据点，由于虫洞的主要技术集中在出口处，这会导致该据点的所有还未被摧毁的虫洞被一同摧毁。而从这个据点出发的虫洞则不会摧毁。

注意：摧毁只会导致虫洞不可用，而不会消除它的存在。

为了抗击敌人并维护各部队和各据点之间的联系，我方发展出了两种特种部队负责修复虫洞：

• A 型特种部队则可以将某个特定的虫洞修复。
• B 型特种部队可以将某据点的所有损坏的虫洞修复。

考虑到敌人打击的特点，我方并未在据点上储备过多的战略物资。因此只要这个据点的某一条虫洞被修复，处于可用状态，那么这个据点也是可用的。

我方掌握了一种苛刻的空间特性，利用这一特性我方战舰可以沿着虫洞瞬移到敌方阵营，实现精确打击。

为了把握发动反攻的最佳时机，指挥部必须关注战场上的所有变化，为了寻找一个能够进行反攻的时刻。总指挥认为：

• 如果从我方的任何据点出发，在选择了合适的路线的前提下，可以进行无限次的虫洞穿梭（可以多次经过同一据点或同一虫洞），那么这个据点就可以实现反击。
• 为了使虫洞穿梭的过程连续，尽量减少战舰在据点切换虫洞时的质能损耗，当且仅当只有一个从该据点出发的虫洞可用时，这个据点可以实现连续穿梭。
• 如果我方所有据点都可以实现反击，也都可以实现连续穿梭，那么这个时刻就是一个绝佳的反攻时刻。

总司令为你下达命令，要求你根据战场上实时反馈的信息，迅速告诉他当前的时刻是否能够进行一次反攻。

\(1 \le n \le 5 \times {10}^5\)，\(1 \le m \le 5 \times {10}^5\)，\(1 \le q \le 5 \times {10}^5\)。

考虑给每个点随机一个权值 \(w_i\)

那么发现所有点的出度均为一就是统计每条边的起点所在点的点权和所有点的权值和一致。

于是我们对每个点维护一下以它为终点的失活的边的起点点权和以及激活的边的起点点权和就行。

时间复杂度 \(O(n+ m+ q)\)。

22 Noip 喵了个喵

小 E 喜欢上了一款叫做《喵了个喵》的游戏。这个游戏有一个牌堆和 \(n\) 个可以从栈底删除元素的栈，任务是要通过游戏规则将所有的卡牌消去。开始时牌堆中有 \(m\) 张卡牌，从上到下的图案分别是 \(a_1, a_2,\dots, a_m\)。所有的卡牌一共有 \(k\) 种图案，从 \(1\) 到 \(k\) 编号。牌堆中每一种图案的卡牌都有偶数张。开始时所有的栈都是空的。这个游戏有两种操作：

• 选择一个栈，将牌堆顶上的卡牌放入栈的顶部。如果这么操作后，这个栈最上方的两张牌有相同的图案，则会自动将这两张牌消去。
• 选择两个不同的栈，如果这两个栈栈底的卡牌有相同的图案，则可以将这两张牌消去，原来在栈底上方的卡牌会成为新的栈底。如果不同，则什么也不会做。

这个游戏一共有 \(T\) 关，小 E 一直无法通关。请你帮小 E 设计一下游戏方案，即对于游戏的每一关，给出相应的操作序列使得小 E 可以把所有的卡牌消去。

对于所有数据，保证 \(S \leq 2 \times 10^6\)，\(1 \leq n \leq 300\)，\(1 \leq a_i \leq k\)。

我们先来考虑 \(k = 2n − 2\) 怎么做。

这个部分是简单的，我们直接每个栈放两个数，留一个空栈。

进来一个已经出现过的数，就根据之前出现的时候在栈顶还是栈底然后操作就行。

\(k = 2n − 1\) 的时候，我们依然考虑延续这个思路：尽量保持 \(n − 1\) 个栈里放 \(2\) 个元素，留一个空栈的状态。

考虑什么时候我们不能维持这个状态了，也就是 \(n − 1\) 个栈都已经放了 \(2\) 个元素了，然后再进来了一个没出现的元素，我们设这个元素为 \(x\)。

关键在于这个时候我们怎么操作来保持我们想要保持的状态。

我们考虑一下放 \(x\) 之后到下一次 \(x\) 出现的位置这段区间。

如果这段区间里的数全是现在栈顶的数，那就直接把 \(x\) 放空栈就行，因为后面只会出/入栈顶，用不到空栈处理底的操作，等到第二个 \(x\) 来的时候这个栈就又能空出来了。

否则，就是说这个区间至少存在一个数是现在某个栈的栈底，我们记最早出现的那个栈底是 \(u\)，\(u\) 所在的栈的栈顶是 \(v\)。

考虑从当前到 \(u\) 最早出现时，\(v\) 出现的次数：

• 如果 \(v\) 出现偶数次，那就把 \(x\) 放这个栈栈顶，后面来的 \(v\) 都丢在空栈里，最后空栈会空出来，然后放 \(u\) 消掉。

• 如果 \(v\) 出现奇数次，那就把 \(x\) 放空栈，后面来的 \(v\) 丢在栈顶，这样 \(u\) 来的时候 \(v\) 已经被奇数个 \(v\) 干掉了，可以直接丢进栈里面。

\(O(m)\)

22 Noip 比赛

给定两个长度为 \(n\) 的序列 \(a, b\) 有 \(q\) 次询问，每次询问会给出两个整数 \(l, r\), 求：

\(\sum_{x = l}^{r}\sum_{y = x}{r}(\max_{i = x} ^ y a_i)(\max_{i = x}^{y} b_i)\)

\(1 \le n, q \le 2.5 \times 10^5\)

我们离线所有询问，对右端点 \(r\) 进行扫描线。

在扫描过程中, 我们设 \(X_l\) 和 \(Y_l\) 分别表示 \(a_{l...r}\) 和 \(b_{l...r}\) 的最大值。

在扫描右端点的同时, 我们维护 \(a, b\) 的单调栈，这样如果扫描到 \(i\)，\(i\) 弹栈弹掉的区间的 \(X\) 就会修改为 \(a_i\)，\(Y\) 会修改为 \(b_i\)。

如果我们要查询的 \(l,r\) 的答案, 那么相当于在扫描到 \(r\) 的时候, 查询区间 \([l,r]\) 的历史 \(X × Y\) 和。

对每个位置 \(i\) 再维护历史 \(X_i × Y_i\) 和 \(sum_i\)，现在需要支持的操作就是：

• 对 \(X\) 区间加。
• 对 \(Y\) 区间加。
• 对所有 \(i\)，更新 \(sum_i ← sum_i + X_i × Y_i\)。
• 对 \(sum\) 询问区间和。

对序列建立线段树，每个线段树结点维护 \(s_x,s_y,s_{xy},s_{sum}\) 分别表示区间内 \(x, y, x × y,sum\) 的和。

还需要维护若干标记 \(add_x, add_y\) 表示区间加 \(x\) 和区间加 \(y\) 的标记，

此外还有一些关于历史和的标记 \(upd, h_x, h_y, h_{xy}\)

分别表示还有几次 \(sum_i ← sum_i + x_i × y_i\) 的历史累加操作没下放，

这几次没下放的操作的 \(add_x\) 之和，\(add_y\) 之和，\(add_x × add_y\) 之和。

整理好要维护哪些标记后，逐个耐心推下怎么下传就行。

\(O((n + q)\log n)\)。

还有一种更好想的方式，是把状态写成矩阵形式，矩阵维护长度，序列 \(x\) 的和，序列 \(y\) 的和，\(x_i × y_i\) 的和和历史和。
每个节点的矩阵都是两个儿子的矩阵的和，每次更新就是乘一个矩阵，然后矩阵乘法有结合律和分配率，那么每次更新也是可以打 \(tag\) 的。

这样朴素实现就能做到 \(O(5^3q \log n)\)。

可以把矩阵写出来，注意到需要维护的矩阵本质不同的数只有 \(7\)个，直接维护那 \(7\) 个数然后手动矩乘即可。

21 Noip 方差

给定长度为 \(n\) 的非严格递增正整数数列 \(a\) 每次可以进行操作：

• 任选一个正整数 \(1 < i < n\) 将 \(a _ i\) 变为 \(a_{i -1} + a_{i + 1} - a_i\)

求在若干次操作之后，该数列方差最小值是多少

\(1 \le n \le 400, a_i \le 600 或者 1 \le n \le 10^4, a_i \le 50\)

先将答案化为 \(n\sum_i a_i^2 - (\sum_i a_i)^2\)

容易证明，操作对数列的影响就是交换差分数组的相邻两项。

一个重要的结论是，最优情况下，这个新的差分序列必然是一个单
谷序列。证明在之后会给出。

考虑将所有差分从小到大排序后依次插入，令 \(f_{i,j}\) 表示已经考虑了前 \(i\) 个差分值，现有的 \(a_i\) 之和为 \(j\) 时的 \(\sum_i a_i^2\) 的最小值。

令 \(d_i,s_i\) 分别表示差分值和差分值的前缀和。

转移就考虑放最左边还是最右边：

• 最左边：\(f_{i - 1, j} + d_i^2 \times i + 2 \times j \times d_i \to f_{i, j + i \times d_i}\)
• 最右边：\(f_{i - 1, j} + s_i^2 \to f_{i, j + s_i}\)

答案就是 \(\min_i(n \times f_{n, i} - i ^2)\)

这样直接做复杂度是 \(O(n^2v)\) 的，但是 \(d_i = 0\) 的时候是不用转移的，
所以可以做到 \(O(n \min(n, v)v)\)。

上面提到的结论的证明：

\(n\sum_i a_i - (\sum_i a_i) ^ 2\)

\(= n\sum_i ( \sum_{j \le i} d_j) ^2 - (\sum_i \sum_{j \le i} d_j)^2\)

\(= n\sum_j \sum_k d_j d_k (n - max(j, k)) - \sum_j \sum_k d_j d_k (n - j)(n - k)\)

\(=\sum_j \sum_k d_j d_k(-n \times max(j, k) + n(j + k) - jk)\)

\(=\sum_j \sum_k d_j d_k(n \times min(j, k) - jk)\)

\(=\sum_i d_i^2(n - i) + 2\sum_j \sum_{j < k} d_j d_k (n - k)j\)

注意到对于 \(i > n/2\)，如果 \(d_i > d_{i+1}\)，交换两者会让两个 \(\sum\) 都变小。

同理对于 \(i ≤ n/2\)，如果 \(d_i < d_{i+1}\)，交换两者会让两个 \(\sum\) 都变小。

因此最优的差分序列是一个单峰序列。

21 Csp-S 交通规划

有一个 \(n \times m\) 的网格，里面有 \(2mn - m - n\) 条线段，外面还有 \(2m + 2n\) 条射线，他们都带有一个权值。

\(T\) 次给定 \(k\) 个在某几条射线上的点，他们已经被染成黑色和白色，需要求出将整个网格染色后，端点颜色不同的边的最小权值和。

\(1 \le n, m \le 500, T \le \sum k \le 50\)

先考虑 \(k = 2\), 若此时两个附加点颜色相同，显然答案为 \(0\)，否则整
张图一定会被染成一白一黑的两个连通块。

相当于就是找到一条从左边的平面到右边平面的一条路把两个点割
开。

考虑多个询问点时，那么这个网格图上被钦定的颜色必定两色交替，
且个数为偶数。

效仿 \(k = 2\)，我们相当于是要把这几段隔开来。也就是红-蓝间隔和
蓝-红间隔两两匹配，使得匹配的路径和最小，两两之间的最短切割
路径可以通过建平面图跑最短路得到。

至于最小权匹配，可以直接 KM 或者费用流，当然由于这个题特殊
性质也可以区间 DP（因为分割线交叉了可以看作不交叉，看作在
接头的地方碰头再分开）。
\(O(knm \log (nm) + k^3)\)

20 Noip 移球游戏

给定 \(n + 1\) 个栈，栈的高度限制为 \(m\)。

初始时前 \(n\) 个上每个有 \(m\) 个球，最后一个为空。

球分为 \(n\) 种颜色，每种恰好 \(m\) 个。

一次操作可以把一个栈顶的元素弹出放到一个另一个栈顶，但是不可以使栈溢出或下溢。现要把同种颜色的球移动到同一个栈上。

你需要构造一个在 \(820000\) 次操作内的方案。
\(2 ≤ n ≤ 50, 2 ≤ m ≤ 400\)

先考虑构造 \(n = 2\) 时的方案。
我们设原来第 \(1\) 根柱子上有 \(s\) 个 \(1\)，然后我们就进行以下操作：

图炸了？

于是我们可以在 \(O(m)\) 次操作内把两个栈里的 \(m\) 个扔到第一个栈中，再把另外 \(m\) 个扔到第二个栈中。

对于多种颜色，我们考虑把其转化到两种颜色求解。

考虑分治，先将颜色在 \([l, mid]\) 中的球都扔到编号在 \([l, mid]\) 的栈里，\([mid + 1,r]\) 同理，然后递归求解。

具体怎么分的，就是拿两个指针一开始分别指向 \(l\) 和 \(mid + 1\)，每次看看这两个指针指向的栈里的数是 \([l, mid]\) 更多还是 4[mid + 1,r]$ 更多，

如果是前者，就移动 \(m\) 个 \([l, mid]\) 到 \(i\)，然后给 \(i\) 加一；否则移动 \(m\) 个 \([mid + 1,r]\) 到 \(j\)，然后给 \(j\) 加一。

\(O(nm \log n)\)

20 Noip 微信步数

有一个 \(k\) 维场地，第 \(i\) 维宽为 \(w_i\)，即第 \(i\) 维的合法坐标为 \(1, 2, · · · ,w_i\)。

小 C 有一个长为 \(n\) 的行动序列，第 \(i\) 元素为二元组 \((c_i , d_i)\)，

表示这次行动小 C 的坐标由 \((x_1, x_2,..., x_k)\) 变为
\((x_1, x_2, . . . ,x_k)\)。

小 C 会将行动序列重复无限次，直到走出这个场地。

接下来，小 C 会以场地中的每个整点为起点，按照行动序列走直到走出场地。

小 C 想知道他一共会走几步。

答案对 \(10^9 + 7\) 取模。

\(1 ≤ n ≤ 5 × 105, 1 ≤ k ≤ 10, 1 ≤ w_i ≤ 10^9, d_i ∈ \{1, −1\}\)

首先将问题转化一下，转为我们对每个 $i 统计有几个起点走 \(i\) 步还没走出去。

不妨直接考虑每个 \(mod n\) 相同的 \(i\)。

令 \(s_d, premx_{i,d}, premn_{i,d}\) 分别表示走了一个周期 \(d\) 维的变化量，走了前 \(i\) 步时向正方向走的最大位移和向负方向走的最大位移。

对于走了 \(k\) 个完整周期又 \(i\) 步后的第 \(d\) 维来说，需要满足：

1. 如果 sd > 0 则需要满足：

• \(x_d + premn_{n,d} ≥ 1\)
• \(x_d + s_dk + premx_{i,d} ≤ w_i\)
• \(x_d + s_d(k − 1) + premx_{n,d} ≤ w_i\)
• 即 \(1 − premn_{n,d} ≤ x_d ≤ w_i − s_dk − max(premx_{i,d}, premx_{n,d})\)

2. 如果 sd < 0，同理我们可以得到：\(1 − s_dk − min(premn_{i,d}, premn_{n,d} − s_d) ≤ x_d ≤ w_x − premx_{n,d}\)

3. 如果 \(s_d = 0\)，可以得到 \(1 − premn_{n,d} ≤ x_d ≤ w_i − premx_{n,d}\)

对于每一维，可以算出 \(k\) 最大能是多少，对于一个 \(k\)，对答案的贡献就是 \(∏_i (r_i − l_i + 1)\)。

其中 \(r_i, l_i\) 分别表示 \(i\) 这维能取的起点的上界和下界。

根据前面我们的推导，\(r_i − l_i + 1\) 应该是一个关于 \(k\) 的一次函数，若干个关于 \(k\) 的一次函数乘起来，那就是关于 \(k\) 的一个多项式。

也就是说现在是有个多项式 \(f(x)\)，我们要求 \(f(1) + f(2) + · · · + f(lim_k)\)，\(lim_k\) 表示 \(k\) 的上界，对多项式做前缀和, 依旧是多项式，只是最高次会增加一，于是直接插值即可。

\(O(nk)\)

19 Csp-S 树上的数

给定一棵树和每个节点上的初始数字，初始数字构成了一个排列，
删除一条边的效果是交换被这条边连接的两个节点上的数字交换。

设 \(p_i\) 表示删完 \(n − 1\) 条边后 \(i\) 在哪个节点，要求合理安排删除 \(n − 1\) 条边的删除顺序，使得排列 \(p\) 字典序最小。

\(1 ≤ n ≤ 2000\)

考虑把一个数字从一个节点运送到另一个节点的过程。

相当于给路上经过的边安排了一个删除顺序的限制。

可以发现，限制总共有 \(3\) 种：

• 对于起点，选择的边要求是这个点所有边中第一条删除的；
• 对于中间的点，要求选择的两条边的删除顺序必须连续；
• 对于终点，选择的边要求是这个点所有边中最后一条删除的。

那么考虑对于每个点分别都建立一张图，图上面的点代表这个点连
出去的一条边。

在这张图上的一条有向边代表出点要在入点之后马上选择，同时记
录这个点钦定的第一条边和最后一条边。每个点的图不相关。

那么考虑贪心，从小到大确定每个数字的最终位置，同时保证不矛
盾。

矛盾的情况有三种：

• 图的形式不是若干条链的形式；
• 第一个点（边）有入边，最后一个点（边）有出边；
• 第一个点（边）所在的链的链尾是最后一个点（边），但是还有其他的点不在链中。

从每个数字的起始点出发，保证从根到这个点的路径不会引起矛盾，更新答案即可。

具体图的情况可以用并查集维护

\(O(n^2\alpha(n))\)

17 Csp-S 宝藏

给定一张 \(n\) 个点，\(m\) 条边的有重边的无向带权图。

你需要确定一个根，然后找到一棵生成树使得所有边，边权和到根的距离的乘积的和最小。

\(n ≤ 12\)

考虑一层一层铺这个生成树，令 \(f_i,S,S′\) 表示当前生成树已经铺了 \(i\) 层了，已经在生成树的点集为 \(S\)，第 \(i\) 层的点集为 \(S'\)。

转移就考虑新加入一个子集作为新的一层，新加入的每个点显然是连向 \(S'\) 中和他有边的且边权最小的点，这个可以预处理。

这样的话复杂度是 \(O(n4^n)\) 的，实现精细一点可以过。

但其实，\(S′\) 这一维完全是可以省略的

因为如果我们连向的点实际并不是在第 \(i\) 层的，这个方案必然不会是最优的（因为不如在连向的点的下一层就加入这个点，而不是现在加入），而我们这样 DP 也能覆盖到所有的情况，因此这样就是
对的！

这样的话，复杂度就是 \(O(n3^n)\) 了。

标签：11,le,sum,times,据点,ch,Day,dp
From： https://www.cnblogs.com/qinzh/p/17604388.html