岱陌广场

分享算法思考、训练复盘与日常交流。

P1063 能量项链题解

zhangze 2026-4-4 21:55:05

P1063 能量项链题解题意简述给定一个链，链上有

N

个珠子，不同珠子合并会产生不同的能量，问：按照什么样的顺序合并这

N

个珠子能产生最大的能量？题目分析

因为题目中所给的是环，我们需要将其转化为链，可以将环断开，拼成一个长度为 $2N$ 的长链，每个新链上第 $i + N$ 颗珠子都对应着原链上第 $i$ 颗珠子。

接下来就需要考虑利用区间 $dp$ 算法，来进行状态定义：

定义

dp[i][j]

表示将区间

[i, j]

的珠子合并为一颗珠子所产生的能量（当然是最大的）。

状态转移方程：考虑用一个分割点

k(i \le k < j)

将区间

[i, j]

分割为

[i, k]

和

[k + 1, j]

两个区间，将这两个区间合并成的珠子进行合并，那么状态便可以这样转移。

区间 $[i,k]$ 合并成一个（头 $h_i$ , 尾 $h_{k + 1}$ ）的珠子；

区间 $[k+1, j]$ 合并成一个（头 $h_{k + 1}$ , 尾 $h_{j + 1}$ ）的珠子；

那么新合并地珠子便可以表示成三个部分

$f[i][k]$ ，
$f[k + 1][j]$
$h_i \times\ h_{k + 1} \times\ h_{j + 1}$

所以总能量为$f[i][k] + f[k + 1][j] + h_i \times\ h_{k + 1} \times\ h_{j + 1}$

我们可以通过枚举分割点 $k(i \le\ k < j)$ 来求合并产生能量的最大值

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 105;
int n, h[N * 2], f[N * 2][N * 2];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n; i++) {
        cin >> h[i];
        h[i + n] = h[i];
    }
    for(int l = 2;l <= n; l++) {
        for(int i = 1;i <= 2 * n - l; i++) {
            int j = i + l - 1;
            for(int k = i;k < j; k++) {
                f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + h[i] * h[k + 1] * h[j + 1]);
            }
        }
    }
    int ans = 0;
    for(int i = 1;i <= n; i++) ans = max(ans, f[i][i + n - 1]);
    cout << ans;
    return 0;
}

时间复杂度：

O(N ^3)

（适用于

N \le\ 10 ^ 2

的数据）空间复杂度：

O(N^2)

结语考场上能识别出这道题考查的是区间

dp

算法才是关键，根据状态定义来推出状态转移方程！

113 浏览0 点赞0 收藏0 评论

绿【树形动态规划、DFS序】选课

YIZHIYANG初来乍到 2026-4-1 20:44:55

绿【树形动态规划、DFS序】选课题意概括给定包含

N

个节点与

N

个选取配额的依赖网络。节点

i

具有权值

s_i

与唯一的直接前置依赖节点

k_i

（若

k_i=0

则无依赖）。依赖关系整体构成森林拓扑。现要求在严格满足拓扑依赖律（即选取节点

i

的必要条件为节点

k_i

已被选取）的前提下，选取恰好

M

个节点，最大化所选节点的权值总和。数据范围：

1 \leq N, M \leq 300

，

0 \leq k_i \leq N

，

1 \leq s_i \leq 20

。样例分析针对给定样例，我们可引入权值为

0

的虚拟根节点

0

。依赖森林即转化为以

0

为根的有向树。其拓扑结构映射如下：节点

0

连向子节点

2, 3

；节点

2

连向子节点

[k+1, j]

；节点

7

连向子节点

5, 6

。目标等价于在包含节点

0

的前提下，自该树中选取

M+1 = 5

个节点。依据贪心与局部最优结构，最优子树组合为选取节点集合

\{0, 2, 3, 7, 6\}

。对应权值总和求值为：

0 + 1 + 4 + 2 + 6 = 13

此即理论最大收益。题目分析常规的树上背包动态规划算法在合并子树状态时，需利用嵌套循环枚举各子树分配的容量，其状态转移的时间开销会导致整体时间复杂度退化至

\mathcal{O}(N M^2)

。为严密贴合

\mathcal{O}(NM)

的最优渐进下界，我们需要对树形依赖关系进行降维，引入 DFS 序（深度优先搜索遍历序列）将树上问题同构映射为线性序列问题。定义

dfn[i]

为树的前序遍历序列中第

i

个被访问的节点标号，并设

sz[u]

为以

u

为根的子树的节点基数。此时建立二维状态矩阵：令

f[i][j]

表示仅考虑 DFS 序的后缀区间

[i, N+1]

，且选取恰好

j

个节点时所能获取的最大权值。对于位于 DFS 序第

i

位的节点

u = dfn[i]

，面临二元决策：

若决策不选取节点

u

，受限于拓扑约束律，其所有后代节点均不可达。此时序列处理指针必须发生跃迁，直接跨越整棵子树，转移至

i + sz[u]

的位置。

若决策选取节点

u

，则状态合法化，序列处理指针推进至 DFS 序的紧邻后继

i + 1

（即其首个子节点），且剩余可选容量衰减

1

。

由此可提取形式化的状态转移方程：初始边界条件设为：

f[N+2][0] = 0

，其余状态初始化为

-\infty

。我们对 DFS 序列执行自底向上的逆序动态规划推演，最终所求的全局最优解即收敛于

f[1][M+1]

。该模型状态总数严格为

\mathcal{O}(NM)

，且每次转移的计算代价为

\mathcal{O}(1)

，从根本上消除了分配多项式复杂度的可能。参考实现#include<bits/stdc++.h> using namespace std; using ll = long long; int n, m; int h[305], nxt[305], to[305], edg; int val[305], sz[305], dfn[305], id; int f[305][305]; void add(int u, int v) { to[++edg] = v; nxt[edg] = h[u]; h[u] = edg; } void dfs(int u) { dfn[++id] = u; sz[u] = 1; for (int i = h[u]; i; i = nxt[i]) { int v = to[i]; dfs(v); sz[u] += sz[v]; } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= n; ++i) { int k, s; cin >> k >> s; add(k, i); val[i] = s; } dfs(0); for (int i = 0; i <= id + 1; ++i) { for (int j = 0; j <= m + 1; ++j) { f[i][j] = -1e9; } } f[id + 1][0] = 0; for (int i = id; i >= 1; --i) { int u = dfn[i]; for (int j = 0; j <= m + 1; ++j) { f[i][j] = f[i + sz[u]][j]; if (j > 0) { f[i][j] = max(f[i][j], f[i + 1][j - 1] + val[u]); } } } cout << f[1][m + 1] << "\n"; return 0; }复杂度分析时间复杂度：

\mathcal{O}(NM)

。预处理阶段的前序遍历耗时

\mathcal{O}(N)

，动态规划阶段的状态空间规模为

(N+1) \times (M+1)

，单个状态转移的计算步数为严格常量级

\mathcal{O}(1)

，故渐进时间复杂度上界为

\mathcal{O}(NM)

。空间复杂度：

\mathcal{O}(NM)

。状态矩阵的阶数为

N \times M

，图与序列所占用的线性表空间均为

\mathcal{O}(N)

。整体内存开销受限于状态矩阵，渐进空间复杂度为

\mathcal{O}(NM)

。https://www.luogu.com.cn/problem/P2014

115 浏览1 点赞0 收藏0 评论

202603七级

黑大帅 2026-3-14 19:57:39

T1 题目题目描述若求

\prod_{i=1}^{k} a_i

的最大值。输入格式第一行输入整数

T \quad (1 \le T \le 10^4)

表示测试组数。接下来

T

行，每行输入一个整数

n

。输出格式输出

M

行。每行输出最大乘积

\prod_{i=1}^{k} a_i \bmod 10^9

数据范围

40% 数据： $1 \le n \le 50$

所有数据： $1 \le n \le 10^6$

题解这是一个非常经典的问题：整数拆分最大乘积即：

把 $n$ 拆成若干正整数，使乘积最大。

40 分 DP / 完全背包做法因为

n \le 50

，每次

O(n^2)

就够了。40 分做法可用完全背包。设

dp[i]

表示和为

i

时的最大乘积。把每个正整数

x

看作一种可无限选取的物品，体积为

x

，收益为乘法因子

x

。转移为

dp[s]=\max(dp[s],dp[s-x]\times x)

初值

dp[0]=1

，最终输出

dp[n]

。把每个正整数

x

看成一种“物品”：

体积 = $x$

价值不是加法，而是乘法中的一个因子 $x$

我们希望选若干个物品，使总体积恰好为

n

，并让这些数的乘积最大。因为每个数可以取任意次，所以这本质上就是完全背包。这就是一个“恰好装满”的完全背包，只不过普通背包是“价值相加”，这里变成了“乘积最大”。如果直接这样写，那么对于

n=2

：

不拆：2

拆：1+1，乘积 1

题目要求是“若

a_1+\cdots+a_k=n

1\le k\le n

”
其实是允许

k=1

的，也就是允许不拆。那么最终答案就是：

dp[n]

并且转移时把

j=i

也允许即可。代码（完全背包写法）#include<bits/stdc++.h> using namespace std; using ll = long long; const ll mod = 1e9; int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while(T--) { int n; cin >> n; ll dp[55]; for(int i = 0; i <= n; i++) dp[i] = 0; dp[0] = 1; for(int i = 1; i <= n; i++) { for(int j = 1; j <= i; j++) { dp[i] = max(dp[i], dp[i - j] * j); } } cout << dp[n] % mod << "\n"; } return 0; }为什么这就是完全背包因为：

每个整数 $x$ 都可以选很多次

每次选一个 $x$ ，就相当于消耗容量 $x$

最终总和恰好要到 $n$

这和完全背包“每种物品无限件”完全一致。只不过普通背包是：

dp[s]=\max(dp[s],dp[s-x]+v)

这题变成：

dp[s]=\max(dp[s],dp[s-x]\times x)

所以本质没变，只是“加法价值”换成了“乘法价值”。复杂度每组数据：

O(n^2)

在

n \le 50

时非常轻松。满分做法最优策略是：尽量拆成 3至于为什么，证明可以去以下这篇文章去看数学结论：当

n ≥ 5

时

3 \times (n-3) > n

说明拆出 3 会更优。分类讨论情况1：n % 3 = 0全部拆成3

3^{n/3}

情况2：n % 3 = 1例如：10 = 3 + 3 + 3 + 1但3 + 1 = 4更优：3 + 3 + 4所以

3^{(n/3-1)} \times 4

情况3：n % 3 = 2直接多一个2

3^{n/3} \times 2

特殊情况n = 1 → 1 n = 2 → 1 n = 3 → 2时间复杂度每个查询

O(\log n)

快速幂即可。T1 参考代码#include<bits/stdc++.h> using namespace std; using ll = long long; const ll mod = 1e9; ll ksm(ll a,ll b) { ll r = 1; while(b) { if(b&1) r = r * a % mod; a = a * a % mod; b >>= 1; } return r; } int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while(T--) { ll n; cin >> n; if(n==1) cout<<1<<"\n"; else if(n==2) cout<<2<<"\n"; else if(n==3) cout<<3<<"\n"; else { ll a = n/3; ll b = n%3; if(b==0) cout<<ksm(3,a)<<"\n"; else if(b==1) cout<<ksm(3,a-1)*4%mod<<"\n"; else cout<<ksm(3,a)*2%mod<<"\n"; } } }T2 题目题目描述有

n

个城市，编号

1 \sim n

。有

m

条无向公路。每条公路有：

费用 $w_i$

风景好看度 $b_i$

汽车要从 1 号城市到 n 号城市。规则：可以 免去路径上一条风景好看度最高的公路费用
（如果有多条同样最高，只能免去一条）。求 最小总费用。若无法到达，输出-1输入格式第一行n m接下来

m

行u v w_i b_i表示一条连接

u,v

的无向边

费用 $w_i$

风景值 $b_i$

输出格式输出从

1

到

n

的最小费用。数据范围

1 \le n,m \le 5000

1 \le w_i,b_i \le 10^9

T2 题解这题难点不在最短路本身，而在于：

99 浏览1 点赞0 收藏0 评论

USACO-26-1-铜组

黑大帅 2026-1-10 8:32:55

T1 chip change题目描述奶牛 Bessie 手里有 A 个 A 类筹码，以及 B 个 B 类筹码（

0\le A,B\le 10^9

）。她可以进行如下操作任意多次：

如果当前 至少有 $c_B$ 个 B 类筹码，就可以用 $c_B$ 个 B 类筹码兑换 $c_A$ 个 A 类筹码。
其中

1\le c_A,c_B\le 10^9

。

现在问：最小的非负整数

x

是多少，使得满足下面的“保证”条件：

在 Bessie 额外收到 $x$ 个随机筹码之后（每个筹码可能是 A 类或 B 类，分配方式未知），无论这 $x$ 个筹码具体怎么分配成 A/B，Bessie 都一定能通过若干次兑换操作，使得最终拥有的 A 类筹码数量 至少为 $f_A$ （ $0\le f_A\le 10^9$ ）。

你需要对每个测试用例输出这个最小的

x

。输入格式第一行是整数

T

，表示测试用例个数（

1\le T\le 10^4

）。接下来

T

行，每行包含 5 个整数：

0

输出格式对每个测试用例输出一行一个整数：对应的答案

x

。

注意：数据范围很大，可能需要 64 位整数类型（例如 C/C++ 的 long long）。

样例样例输入1:2 2 3 1 1 6 2 3 1 1 4样例输出1:1 0样例输入1:5 0 0 2 3 5 0 1 2 3 5 1 0 2 3 5 10 10 2 3 5 0 0 1 1000000000 1000000000样例输出2:9 8 7 0 1000000000000000000并解释（原文意思）：

第 1 组（ $A=B=0,c_A=2,c_B=3,f_A=5$ ）：
Bessie 一开始没有筹码。只要她额外收到任意 9 个筹码，不管这 9 个里 A/B 怎么分配，她都能通过兑换最终得到至少 5 个 A。
比如她收到 2 个 A 和 7 个 B，可以兑换两次得到 6 个 A（ $\ge 5$ ）。
但如果只收到 8 个 B，则最多兑换 2 次得到 4 个 A（<5），所以 8 不够。

第 4 组：她一开始就已经有足够多的 A，因此答案是 0。

评分提示

输入 3：

c_A=c_B=1

输入 4-5：所有用例的

x\le 10

输入 6-7：

c_A=2, c_B=3

输入 8-12：无额外限制

参考代码#include <bits/stdc++.h> using namespace std; using ll = long long; using i128 = __int128; ll a, b, ca, cb, fa; i128 cal(ll y, ll tot) { return (i128)tot - y + ((i128)y / cb) * ca; } bool chk(ll x) { ll tot = a + b + x; ll lim = b + x; i128 mn = cal(lim, tot); ll tg = cb - 1; if (ca > cb) { ll r = b % cb; ll d = (tg - r + cb) % cb; ll y = b + d; if (y <= lim) mn = min(mn, cal(y, tot)); } else { ll r = lim % cb; ll d = (r - tg + cb) % cb; ll y = lim - d; if (y >= b) mn = min(mn, cal(y, tot)); } return mn >= fa; } void sol() { cin >> a >> b >> ca >> cb >> fa; ll l = 0, r = 2e18, ans = 2e18; while (l <= r) { ll md = l + (r - l) / 2; if (chk(md)) { ans = md; r = md - 1; } else { l = md + 1; } } cout << ans << "\n"; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { sol(); } return 0; }T2 COW题目描述Bessie 得到一个正整数

N

和一个长度为

3N

的字符串

S

。字符串

S

的生成方式如下：把

N

个长度为 3 的字符串拼接起来，而每个长度为 3 的字符串都是 "COW" 的一个循环移位（cyclic shift），也就是说每段只能是下面三种之一：

"COW"

"OWC"

"WCO"

平方串（square string）字符串

X

被称为 平方串，当且仅当存在某个字符串

Y

，使得：

f[1][M+1]

其中

+

表示字符串拼接。例如：

"COWCOW"、"CC" 是平方串（分别对应 $Y="COW"$ 、 $Y="C"$ ）

"COWO"、"OC" 不是平方串

操作一次操作中，Bessie 可以从

S

中删除任意一个子序列

T

，要求

T

是一个平方串。子序列指：从原串中删除若干个字符（可以删除 0 个），保持剩余字符的相对顺序得到的字符串。目标你需要判断：是否可以通过若干次操作，把

S

变成空串。如果可以，还要输出一种删除方案。参数

k

与操作次数要求题目还给一个参数

k\in\{0,1\}

。设你输出的方案使用了

M

次操作。

若

N \times M

：必须保证

\mathcal{O}(N)

等于最少可能操作次数（最优）。

若

k=1

：允许

M

最多为 最少操作次数 + 1（几乎最优，多一次也行）。

输入格式第一行包含两个整数：

T

：测试组数（

1\le T\le 10^4

）

k

：参数（

0\le k\le 1

）

每个测试用例包含：

一行整数

N

（

1\le N\le 10^5

）

一行字符串

S

，长度为

3N

保证所有测试中

N

的总和不超过

10^5

。输出格式对每个测试用例，按如下方式输出：

如果无法把 $S$ 变成空串：输出一行 -1

否则：

第一行输出 $M$ ：你的方案操作次数
第二行输出 $3N$ 个整数，用空格分隔
第 $i$ 个整数 $x_i$ 表示：原串 $S$ 的第 $i$ 个字符是在第 $x_i$ 次操作中被删除的（要求 $1\le x_i\le M$ ）

样例样例输入13 1 3 COWOWCWCO 4 WCOCOWWCOCOW 6 COWCOWOWCOWCOWCOWC样例输出1-1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 2 3 3 2 1 1 1 1 1 1 1 1 1 1 1 1样例解释1

对于最后一个测试用例，最优（最少）操作次数是 2，因此当 $k=1$ 时，只要你的构造满足 $M=2$ 或 $1 \le n,m \le 5000$ 都会被判正确（允许比最优多 1 次）。

如果取 $M=3$ ，下面给出一种可行方案：

第一次操作：删除最后 12 个字符。此时剩下字符串为 COWCOW。
第二次操作：删除子序列 WW。此时剩下字符串为 COCO。
第三次操作：删除所有剩余字符。最终变成空串。

124 浏览1 点赞0 收藏0 评论

基础语法训练大纲

黑大帅 2026-1-7 14:39:49

语法A训练大纲

大标题

小标题

核心考察知识点训练

顺序结构

OJ使用与输出

流输出，OJ评测与反馈机制

变量、常量与输入

const 修饰符，常量后缀（011），流输入

基本运算与类型转换

显示与隐式转换，强制类型转换，整数运算，小数运算，字符与 ASCII 码值，上取整：a / b → (a + b − 1) / b；四舍五入取整：a / b → (a + b / 2) / b；

分支结构

if语句

独立判断逻辑，互斥多路分类讨论

if…else语句

if…else if … else语句

switch…case语句

三元表达式

循环结构：while循环 / for循环 / do…while循环

顺序输出

基础循环枚举顺序输出，for/while 基本结构；控制步长；打印格式

倒序输出

倒序输出，逆向循环；边界（>= / >）；反向遍历

指定范围枚举

枚举指定范围：区间枚举模板，包含/不包含端点；步长枚举

while循环变化过程

while 变化过程：循环不变量，终止条件；调试观察（变量变化轨迹）

求和问题

求和累加，条件累加器，筛选求和；避免重复统计

计数器

计数：计数变量设计，分支内计数，多类计数

累乘

累乘：连乘；溢出意识

求最值

求最值：枚举范围求最值，最值更新条件；条件范围最值

标记法可行性与可行解

标记法（标志变量）→ 枚举可行解（可行性问题）

基础数学问题

质数判断，最大公约数，最小公倍数朴素计算，枚举因数对，根号优化

循环嵌套

枚举入门：双重循环结构；计数/求和/最值在嵌套中的位置

枚举排列：三层/多层枚举；去重条件；排列性质

枚举组合：递增下标控制（i<j<k）；组合计数

枚举进阶：剪枝；数学优化；枚举对象优化；贡献计算思想

一维数组基础1

基本存储与IO

一维数组读写，下标习惯，边界与容量

找元素

线性查找：第一次/最后一次出现（基础）

找最值（打擂台）

最值查找，最值位置，最值首次位置，最值末次位置

数组计数

频次统计；桶思想；值域分析

标记数组

存在性标记；去重；简单筛法雏形

元素移动

数组增删改查元素

连续性元素

连续段统计；最长连续；区间判断

大标题	小标题	核心考察知识点训练
顺序结构	OJ使用与输出	流输出，OJ评测与反馈机制
变量、常量与输入	const 修饰符，常量后缀（011），流输入
基本运算与类型转换	显示与隐式转换，强制类型转换，整数运算，小数运算，字符与 ASCII 码值，上取整：a / b → (a + b − 1) / b；四舍五入取整：a / b → (a + b / 2) / b；
分支结构	if语句	独立判断逻辑，互斥多路分类讨论
if…else语句
if…else if … else语句
switch…case语句
三元表达式
循环结构：while循环 / for循环 / do…while循环	顺序输出	基础循环枚举顺序输出，for/while 基本结构；控制步长；打印格式
倒序输出	倒序输出，逆向循环；边界（>= / >）；反向遍历
指定范围枚举	枚举指定范围：区间枚举模板，包含/不包含端点；步长枚举
while循环变化过程	while 变化过程：循环不变量，终止条件；调试观察（变量变化轨迹）
求和问题	求和累加，条件累加器，筛选求和；避免重复统计
计数器	计数：计数变量设计，分支内计数，多类计数
累乘	累乘：连乘；溢出意识
求最值	求最值：枚举范围求最值，最值更新条件；条件范围最值
标记法可行性与可行解	标记法（标志变量）→ 枚举可行解（可行性问题）
基础数学问题	质数判断，最大公约数，最小公倍数朴素计算，枚举因数对，根号优化
循环嵌套	枚举入门：双重循环结构；计数/求和/最值在嵌套中的位置
枚举排列：三层/多层枚举；去重条件；排列性质
枚举组合：递增下标控制（i<j<k）；组合计数
枚举进阶：剪枝；数学优化；枚举对象优化；贡献计算思想
一维数组基础1	基本存储与IO	一维数组读写，下标习惯，边界与容量
找元素	线性查找：第一次/最后一次出现（基础）
找最值（打擂台）	最值查找，最值位置，最值首次位置，最值末次位置
数组计数	频次统计；桶思想；值域分析
标记数组	存在性标记；去重；简单筛法雏形
元素移动	数组增删改查元素
连续性元素	连续段统计；最长连续；区间判断

121 浏览1 点赞0 收藏0 评论

精华

Bellman-Ford与SPFA算法的正确性证明

YIZHIYANG初来乍到 2025-9-17 3:06:38

预备知识与符号约定在开始证明之前，我们首先需要建立一套清晰的数学语言与符号体系。

图的表示：一个带权有向图被表示为

G = (V, E)

，其中

V

是顶点的集合，

E

是边的集合。图中顶点的数量记为

k_i

，边的数量为

|E|

。每条边

(u, v) \in E

都有一个权重（cost），由函数

w: E \to \mathbb{R}

定义。

路径与路径权重：一条从顶点 $1 \leq N, M \leq 300$ 到 $v_k$ 的路径 $p$ 是一个顶点序列 $\langle v_0, v_1, \dots, v_k \rangle$ ，其中对所有的 $i \in [1, k]$ ，边 $(v_{i-1}, v_i) \in E$ 。路径 $p$ 的权重是构成它所有边的权重之和：

w(p) = \sum_{i=1}^{k} w(v_{i-1}, v_i)

最短路径权重：从顶点 $u$ 到顶点 $v$ 的最短路径权重 $\delta(u, v)$ 定义如下：

$$\delta(u, v) = \begin{cases} \min\{w(p) \mid u \xrightarrow{p} v\} & \text{如果存在从 } u \text{ 到 } v \text{ 的路径} \\ \infty & \text{否则} \end{cases} $$

若图中存在从 $u$ 可达的负权环路，且该环路位于某条从 $u$ 到 $v$ 的路径上，那么 $\delta(u, v) = -\infty$ 。

最短路径估计：在算法执行过程中，我们为每个顶点 $v \in V$ 维护一个最短路径的估计值，记为 $d[v]$ 。算法开始时，除了源点 $s$ 的估计值为 $0$ 外，所有其他顶点的估计值均为 $\infty$ 。

松弛操作 (Relaxation)：松弛是所有此类算法的核心操作。对于一条边 $(u, v) \in E$ ，松弛操作试图利用 $x\le 10$ 的当前最短路径估计值 $d[u]$ 来改善 $v$ 的估计值 $d[v]$ 。其过程如下：

if (d[v] > d[u] + w(u, v)) {
    d[v] = d[u] + w(u, v);
    // 可能还会更新 v 的前驱节点 pi[v] = u
}

松弛操作的本质是在问：“经过顶点 $u$ 到达顶点 $dp[n]$ 是否会比当前已知的到达 $v$ 的路径更短？”如果是，则更新 $d[v]$ 。

基于这些定义，我们可以提出几个最短路径所固有的基本性质：

上界性质 (Upper-Bound Property)：对于所有顶点 $v \in V$ ，我们始终有 $d[v] \geq \delta(s, v)$ 。这个性质在初始化后成立，并且在每次松弛操作后依然保持。因为 $d[v]$ 的更新只会在找到一条更短的、实际存在的路径时发生，所以它永远不会低估真正的最短路径。

三角不等式 (Triangle Inequality)：对于任意边 $(u, v) \in E$ ，我们有 $\delta(s, v) \leq \delta(s, u) + w(u, v)$ 。这是最短路径的内在属性，即从 $s$ 到 $v$ 的最短路径，不可能比“从 $s$ 到 $u$ 的最短路径，再沿着边 $(u, v)$ 走到 $k\in\{0,1\}$ ”更长。

当算法终止，且所有

d[v]

都收敛时，如果

M

对所有

v \in V

成立，那么算法就是正确的。Bellman-Ford算法及其正确性证明Bellman-Ford算法通过对图中的所有边进行

|V|-1

轮迭代松弛来计算单源最短路径。其结构异常简洁，背后却蕴含着深刻的动态规划思想。算法描述

初始化：对于图中所有顶点 $v \in V$ ： $d[v] \leftarrow \infty$ $d[s] \leftarrow 0$ （ $s$ 是源点）

迭代松弛：重复 $|V|-1$ 次：对于图中每条边 $(u, v) \in E$ ：执行松弛操作：if (d[v] > d[u] + w(u, v)) d[v] = d[u] + w(u, v);

负权环路检测：对于图中每条边 $(u, v) \in E$ ：如果 d[v] > d[u] + w(u, v) 成立，则报告图中存在负权环路。

正确性证明Bellman-Ford算法的正确性证明分为两个部分：首先证明在没有负权环路的情况下，算法能正确计算出所有最短路径；其次证明算法能检测出负权环路的存在。1. 最短路径计算的正确性我们将通过数学归纳法来证明，在没有负权环路的前提下，经过

|V|-1

轮松弛后，对所有顶点

v \in V

，都有

d[v] = \delta(s, v)

。我们引入一个关键的辅助定义：令

d_i[v]

表示在完成第

i

轮对所有边的松弛操作后，

v

的最短路径估计值。引理：在第

i

轮松弛之后，对于任意顶点

v

，

d_i[v]

是从源点

k=1

到

v

的、边数至多为

i

的所有路径中，权重最小的路径的权重。证明：我们对轮数

i

进行归纳。

基础情况 (Base Case), i = 0: 在第 0 轮（即初始化后）， $d_0[s] = 0$ ， $d_0[v] = \infty$ (对于 $v \neq s$ )。从 $s$ 到 $s$ 的、边数至多为 0 的路径只有一条空路径，权重为 0。因此 $d_0[s]$ 正确。对于任何 $v \neq s$ ，不存在从 $s$ 到 $v$ 的、边数为 0 的路径，其最短路径权重应为 $\infty$ 。因此 $d_0[v]$ 也正确。故引理在 $i=0$ 时成立。

归纳步骤 (Inductive Step): 假设在第 $i-1$ 轮后，引理成立，即 $d_{i-1}[v]$ 是从 $s$ 到 $v$ 的、边数至多为 $i-1$ 的最短路径权重。我们需要证明在第 $i$ 轮后， $d_i[v]$ 是从 $s$ 到 $v$ 的、边数至多为 $i$ 的最短路径权重。

考虑一条从 $s$ 到 $v$ 的、边数至多为 $i$ 的最短路径 $p$ 。该路径有两种可能：

路径 $p$ 的边数至多为 $i-1$ 。在这种情况下，根据归纳假设，其权重已经不小于 $d_{i-1}[v]$ 。在第 $i$ 轮松弛中， $d[v]$ 的值只会减小或不变，所以 $d_i[v] \leq d_{i-1}[v]$ 。因此， $d_i[v]$ 仍然是这条路径权重的下界。
路径 $p$ 的边数恰好为 $i$ 。设路径为 $s \to \dots \to u \to v$ ，其中 $s \to \dots \to u$ 子路径的边数为 $i-1$ 。这条子路径必定是从 $s$ 到 $u$ 的、边数至多为 $i-1$ 的最短路径。根据归纳假设， $d_{i-1}[u]$ 就是这条子路径的权重。在第 $i$ 轮松弛中，算法会遍历到边 $(u, v)$ 并执行松弛操作。此时，会进行比较： $d_i[v] \le d_{i-1}[u] + w(u, v)$ 这表明， $d_i[v]$ 的值不会超过这条 $s \to \dots \to u \to v$ 路径的权重。

综合以上两点，在第 $i$ 轮迭代之后， $d_i[v]$ 的值不会超过任何一条从 $s$ 到 $v$ 的、边数至多为 $i$ 的路径的权重。同时，根据上界性质， $d_i[v]$ 也不会低于真正的最短路径值。因此， $d_i[v]$ 恰好等于从 $s$ 到 $v$ 的、边数至多为 $i$ 的最短路径的权重。

归纳假设成立。

定理：若图

G

不包含从源点

s

可达的负权环路，则经过

|V|-1

轮松弛后，

d[v] = \delta(s, v)

对所有

v \in V

成立。证明：在不包含负权环路的图中，任意两个顶点之间的最短路径必然是简单路径（不含重复顶点）。一条简单路径的边数最多为

|V|-1

。根据我们刚刚证明的引理，在第

|V|-1

轮松弛之后，

d_{|V|-1}[v]

的值等于从

s

到

v

的、边数至多为

|V|-1

的所有路径中的最短路径权重。由于任何一条最短路径的边数都不可能超过

|V|-1

，所以这个值就是真正的最短路径权重

\delta(s, v)

。即，

d_{|V|-1}[v] = \delta(s, v)

。算法正确。2. 负权环路检测的正确性定理：当且仅当图

G

中存在从源点

s

可达的负权环路时，在

115 浏览1 点赞0 收藏0 评论

划分DP

黑大帅 2025-9-17 1:25:49

划分DP划分型动态规划（划分DP）是一种处理特定类型问题的动态规划方法，常用于解决需要将数据结构（如数组、字符串等）划分成若干部分以优化某些目标函数的问题。这类动态规划问题的关键在于找到合适的状态表示和状态转移方程。下面是划分的

DP

一些常见做法：主要分为两种类型：

\color{red}\text{1、确定段数的划分}

\color{blue}\text{1.定义状态}

首先定义动态规划的状态：通常表示为

dp[i][j]

，其中

i

表示数据结构的某个终点（或起点），

j

可能表示划分的段数、划分的方式或其他根据问题需要定义的参数。

\color{blue}\text{2. 状态转移方程}

状态转移是动态规划的核心，需要找到从之前的状态到当前状态的转移方法。对于划分型DP，状态转移方程通常涉及枚举分割点或分割方式，从而将原问题分解为更小的子问题。形式上可能是这样的：$ dp[i][j] = \min 或 \max \{dp[k][j-1] + cost(k, i)\}，其中 k < i。 $这里

w: E \to \mathbb{R}

表示从

k

到

i

划分的代价，根据实际问题的需求，可以是求和、求最大值、求最小值等操作。

\color{blue}\text{3. 初始化}

合理的初始化是动态规划成功的关键。一般而言，

dp[0][0]

或

dp[i][0]

（根据问题定义而定）是比较容易确定的基础状态。有时候可能需要对

DP

数组进行特殊的初始化来适配边界条件。

\color{blue}\text{4. 计算顺序}

决定动态规划的计算顺序，是从小到大（自底向上）还是从大到小（自顶向下），以确保在计算当前状态时，所有需要的前置状态都已被计算。

\color{blue}\text{5. 答案提取}

根据问题的要求，最终的答案可能在中，也可能需要遍历

DP

表的某一行或某一列来找到答案，其中

0

和

m

分别代表数据结构的大小和问题中的其他参数。

n

数组分割问题：给定一个数组，将其分割为

k

个连续的子数组，使得这

k

个子数组的最大和最小。

字符串编辑问题：给定一个字符串，通过分割成若干部分，并对每一部分进行编辑（如反转、替换）来达到某个目标。

任务调度问题：将

h_{k + 1}

个任务分配给

K

个机器处理，每个任务只能分配给一个机器，如何分配以最小化总完成时间或最大化利润。

划分型DP的关键在于理解如何将大问题划分为小问题，并通过动态规划表来优雅地解决这些小问题。每种类型的问题都有其独特之处，因此在实践中需要根据问题的具体情况来调整DP的定义和转移方程。

\color{red}\text{2、不确定段数的划分}

\color{blue}\text{1) 通用模板（枚举最后一段）}

状态： $dp[i]$ 表示前 $i$ 个元素被划成若干段后的最优值（最小/最大看题意）。

转移（不可取空段）：

初始化：

极小化： $0 + 1 + 4 + 2 + 6 = 13$ ，其余设为 $+\infty$ ；
极大化： $dp[0]=0$ ，其余设为 $u$ 。

方案恢复：用 pre[i]=argmin/argmax k 回溯即可。

关键点：把“合法段”的判定（长度区间、区间和上界、max-min 上界等）嵌入到候选 $k$ 的集合定义里，只在合法 $k$ 上取最优。

\color{blue}\text{2) 常见目标类型与套路}

\color{purple}A.

最小化“各段代价之和”

形式： $\mathrm{segCost}(l,r)$ 给定，目标 $\min\sum \mathrm{segCost}$ 。

朴素： $O(n^2)$ 枚举 $d[u]$ 。

优化 1（长度窗 + 区间最小）：若只允许段长 $L\le r-l+1 \le R$ ，

$$dp[i]=\min_{k\in[i-R,\,i-L]} \{ dp[k] + \mathrm{segCost}(k+1,i) \} $$

若 $\mathrm{segCost}$ 只依赖长度或能拆为 $N$ ，可用滑动窗口最小值 / 单调队列 / 线段树把区间最小做成 $O(\log n)$ 或摊还 $O(1)$ 。

优化 2（前缀和 O(1) 算段代价）：若 $\mathrm{segCost}$ 基于区间和/平方和等，预处理 prefix 即可 O(1) 求段代价，整体从 $O(n^2)$ 降到 $O(n^2)$ 的小常数版或配合其他优化进一步降复杂度。

优化 3（凸二次代价 → CHT/Li Chao）：若

\mathrm{segCost}(k+1,i)=(S_i-S_k)^2 + C

则

$$dp[i]=S_i^2 + \min_k \{ dp[k]+C+S_k^2 - 2S_i S_k \} $$

把 $k$ 看成直线 $y = m x + b$ （ $m=-2S_k$ , $b=dp[k]+S_k^2+C$ ），在 $x=S_i$ 处查询最小值，用凸包优化（CHT）/ Li Chao Tree可做到均摊 $O(\log n)$ 。

\color{purple}B.

最少段数（每段需“可行”）

目标：在每段满足约束（如区间和 $3^{n/3} \times 2$ 、max-min $\le D$ ）前提下，最少用多少段覆盖前 $i$ 。

形式：

O(\log n)

两指针 + 维护可行窗口：若可行性关于区间扩张是单调的（如区间和随右端点右移而非降），可用双指针维护最左可行 $L_i$ ，则

dp[i]=1+\min_{k\in[L_i-1,\,i-1]} dp[k]

用队列/多重集/线段树维护区间最小即可 $b_i$ 甚至 $O(n)$ 。

\color{purple}C.

段数-代价联合权衡（拉格朗日/Alien’s Trick）

想“段数不限，但尽量小且总代价也小”，可给每段加罚 $\lambda$ ：

$$f_\lambda[i] = \min_{k<i}\{ f_\lambda[k] + \mathrm{segCost}(k+1,i) + \lambda \} $$

同时维护使用段数 $cnt[i]=cnt[k]+1$ 的最优。

随 $\lambda$ 增大，最优段数单调不增。对 $\lambda$ 二分/三分/步进搜索，即可得到“恰好 $K$ 段”或“至多 $K$ 段”的最优值与方案（常用于把“未知段数”间接转成“控制段数”）。

\color{purple}D.

最大化类（奖励可加）

同理，把

\min

换成

\max

，把不可行段视为

-\infty

即可；优化思路一致。

\color{blue}\text{3) 决策单调性与分治优化（可选）}

若代价函数

w(k,i)

满足四边形不等式/凸性等条件，且最优决策

opt[i]

单调（

opt[i]\le opt[i+1]

），则

dp[i]=\min_{k<i}\{dp[k]+w(k,i)\}

可用分治优化将一层转移从

O(n^2)

降到

O(n\log n)

。
（是否满足条件需按题目 $

100 浏览1 点赞0 收藏0 评论

精华

概率与期望

黑大帅 2025-9-17 1:24:13

概率与期望概率论事件的运算及概率

包含： $0\le A,B\le 10^9$ ，发生 $B$ 时必然发生 $A$ ，发生 $A$ 时不一定发生 $B$ 。

并（和）事件： $A \cup B = A + B$ ， $A$ 发生或 $B$ 发生或两者都发生。

交（积）事件： $A \cap B = AB$ ， $A$ 和 $B$ 同时发生。

差事件： $A - B = A\overline{B} = A - AB$ ， $A$ 发生但 $B$ 不发生， $\overline{B}$ 表示 $B$ 的对立事件。

互斥事件： $AB=\varnothing$ ， $A$ 和 $B$ 不能同时发生。

对立（逆）事件： $A+\overline{A}=S,\quad A\overline{A}=\varnothing$ ， $A$ 发生时 $\overline{A}$ 不发生， $\overline{A}$ 发生时， $A$ 不发生。

独立事件： $P(AB)=P(A)P(B)$

$A$ 发生与否不影响 $B$ 的概率，反之亦然。

若 $A,B$ 独立，则 $dp[n]$ 、 $\overline{A},B$ 、 $\overline{A},\overline{B}$ 也相互独立。
若 $A,B,C$ $A, B, C$ 相互独立，那么
- $A,B,C$ 两两独立(但逆命题不成立)
- $P(ABC)=P(A)P(B)P(C)$ 。

德摩根律：

$$\overline{A\cup B}=\overline{A}\cap\overline{B}\\ \overline{A\cap B}=\overline{A}\cup\overline{B} $$

加法公式（容斥原理）：
$P(A+B)=P(A)+P(B)-P(AB)$
$x$

减法公式：
$P(A-B)=P(A)-P(AB)$

对立事件概率：
$P(\overline{A})=1-P(A)$

条件概率与乘法公式

条件概率：在 $v \in V$ 已发生下 $B$ 的概率。
$P(B\mid A)=\dfrac{P(AB)}{P(A)}$

乘法公式：
$P(AB)=P(A)P(B\mid A)=P(B)P(A\mid B)$

全概率公式与贝叶斯公式（包括在 NOI 大纲内但大概率 useless）

全概率公式（ $\{B_i\}$ 为完备事件组）：

P(A)=\sum_{i=1}^{n}P(B_i)P(A\mid B_i)

贝叶斯（逆概）公式：

P(B_i\mid A)=\dfrac{P(B_i)P(A\mid B_i)}{P(A)}

离散型随机变量（一维）离散型随机变量是指取值为可列（通常是有限或可数无限）集合中某些具体数值的随机变量。分布列随机变量

X

可取值：

X_1,X_2,\dots,X_k

各取值对应的概率为：

P\{X=X_1\},P\{X=X_2\},\dots,P\{X=X_k\}

分布函数

F(x)=P\{X\le x\}。

重要性质 离散型一维随机变量的分布函数可视为前缀和）：

P\{a\le X\le b\}=F(b)-F(a-1)

。数学期望

E(X)=\sum_{i=1}^{n}x_i p_i

若

Y=g(X)

，则

E(Y)=\sum_{i=1}^{n}g(x_i)p_i

性质：

$E(c)=c,\quad E(ax+c)=aE(X)+c$ 。

$E(X\pm Y)=E(X)\pm E(Y)$

若 $X,Y$ 独立，则 $E(XY)=E(X)E(Y)$ 。

方差

D(X)=E(X^2)-E^2(X)

性质：

D(c)=0,\quad D(aX+b)=a^2D(X)

。

D(x\pm y)=D(x)+D(y)\pm 2\operatorname{Cov}(X,Y)

，其中

\operatorname{Cov}(X,Y)=E(XY)-E(X)E(Y)

为协方差。

若

X,Y

独立，则

\operatorname{Cov}(X,Y)=0

，因此

D(X\pm Y)=D(X)+D(Y)

。

常见分布【0–1 分布（伯努利分布）】进行一次独立试验，成功的概率为

p

，失败的概率为

1-p

。（即

n=1

的二项分布）

记作

分布列

数学期望

方差

X\sim B(1,p)

P\{X=0\}=1-p,\; P\{X=1\}=p

E(X)=p

D(X)=p(1-p)

【二项分布】进行

n

次独立试验，每次成功的概率为

p

，失败的概率为

1-p

。

记作

分布列

数学期望

方差

X\sim B(n,p)

P\{X=k\}=\binom{n}{k}p^k(1-p)^{n-k}

E(X)=np

D(X)=np(1-p)

【几何分布】进行独立试验，直到第一次成功为止；成功的概率为

p

，失败的概率为

1-p

。

记作

分布列

数学期望

方差

X\sim G(p)

P\{X=k\}=(1-p)^{k-1}p

E(X)=\dfrac{1}{p}

D(X)=\dfrac{1-p}{p^2}

【超几何分布】从

N

个物体中抽取

n

个物体，其中有

K

个是成功的，

N-K

个是失败的。

记作

分布列

数学期望

方差

X\sim H(N,K,n)

$P\{X=k\}=\dfrac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}$

E(X)=\dfrac{nK}{N}

D(X)=\dfrac{nK(N-K)(N-n)}{N^2(N-1)}

概率与期望 DP与组合数 DP 类似，只是在 DP 转移时结合概率或期望的计算。常见有后效性方程，需要移项或高斯消元处理。【例题 1】Jerry's Protest（纯概率论应用）#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; vector<int> a(n); for(i

记作	分布列	数学期望	方差
$X\sim B(1,p)$	$P\{X=0\}=1-p,\; P\{X=1\}=p$	$E(X)=p$	$D(X)=p(1-p)$

记作	分布列	数学期望	方差
$X\sim B(n,p)$	$P\{X=k\}=\binom{n}{k}p^k(1-p)^{n-k}$	$E(X)=np$	$D(X)=np(1-p)$

记作	分布列	数学期望	方差
$X\sim G(p)$	$P\{X=k\}=(1-p)^{k-1}p$	$E(X)=\dfrac{1}{p}$	$D(X)=\dfrac{1-p}{p^2}$

记作	分布列	数学期望	方差
$X\sim H(N,K,n)$	$P\{X=k\}=\dfrac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}$	$E(X)=\dfrac{nK}{N}$	$D(X)=\dfrac{nK(N-K)(N-n)}{N^2(N-1)}$

137 浏览1 点赞0 收藏0 评论

二群公告

YIZHIYANG初来乍到 2025-6-9 20:03:39

一、群规与交流允许： 题目算法交流、考研/保研/推免经验分享、科研吐槽、生活分享；红包和广告可以发。禁止： 涉政话题、男女对立话题。其他： 拉人进群需要先购买交流群帖子：点击查看二、改名通知请统一群名片格式：地区-昵称例如：北京-一只羊三、福利活动入群测试题：
https://dtoj.team/contest/681dc734e0fa07f1d11a50b5邀请码： YZY彩蛋： AK 返还微信豆。四、资源网络流 PPT：
链接：https://pan.baidu.com/s/1Vfr3cZFiWRfkev7BJ2F-Kg?pwd=1u4p
提取码：1u4p算法课件（卜东波）：
链接：https://pan.baidu.com/s/1Fk96XApt9GBsJbUoQTH27Q?pwd=th6b
提取码：th6b五、购买会员购买永久会员请直接联系群主。WeChat：_y1zh1yang
群主：三金家的Y同学六、公众号学习指南食用指南：
点击查看七、永久会员作者：三金家的Y同学

购买请直接添加上方群主微信。

419 浏览2 点赞0 收藏0 评论

DTZS-Round1-T5-数阵查询

黑大帅 2025-5-6 20:05:03

解析首先看到题目我们可以发现，或者应该要发现，变化

DP

次的这个矩阵的规模是多大；根据题意的变化规律：

当前有数字的方阵填充成

2 \times 2

的大方阵：

在其方阵的右边界和下边界填上当前数阵没有的最小正整数。

不难发现，每多变化一次，规模是

\times 2 + 1

的,所以显然可以得到递推式：记

d_i

为变化

i

次的规模，初始条件

d_0

= 1递推式：

d_i = d_{i - 1} \times 2 + 1

然后思考什么情况下是无解的呢？不难发现，当前给的

A - B = A\overline{B} = A - AB

是超出变化

n

次的规模的，显然是无解的直接输出

-1 \quad -1

;那么对于有解的情况怎么思考呢？有解的情况可以分为两类：

如果 $x,y$ 刚好处于当前变化的这一层的边界上，那么答案就是 $n + 1$

也就是以下情况：

2.如果

x,y

不处于当前变化的这一层的边界上也就是以下情况的其中一种：

不难发现，我们其实都可以把

x,y

映射到

A

区域去，因为

n \le 50

三个区域是由A区域变化过来的；所以如果处于A区域，不需要变化；如果不处于，直接做映射,然后发现，将

x,y

映射到

w(p) = \sum_{i=1}^{k} w(v_{i-1}, v_i)

区域，其实就是找到变化次数少一次的对应的位置；这个时候，我们就不难想到递归了，将当前

h_{j + 1}

转移传递到上一层的对应的节点的位置设映射后的位置为

x',y'

处于

D

区域

\rightarrow

A

x' = x - d_{n - 1},y' = y - d_{n - 1}

处于

C

区域

i

sz[u]

x' = x - d_{n - 1},y' = y

处于

B

区域

i

u = dfn[i]

1\le k\le n

处于

A

区域

S

A

x' = x ,y' = y

然后规模缩小一层，变成大问题的子问题，直接递归即可参考代码#include<bits/stdc++.h> using namespace std; using ll = long long; ll b[45]; ll work(ll n , ll x , ll y){ if(x > b[n] || y > b[n]) return -1; if(x == b[n] || y == b[n]) return n + 1; ll x1 = x , y1 = y; if(x > b[n-1]) x1 = x-b[n-1]; if(y > b[n-1]) y1 = y-b[n-1]; return work(n-1,x1,y1); } int main(){ b[0] = 1; b[1] = 3; for(int i = 2;i <= 20;i++){ b[i] = b[i-1] * 2 + 1; } int t; cin >> t; while(t--){ ll n,x,y; cin >> n >> x >> y; cout << work(n,x,y) << "\n"; } return 0; }

104 浏览1 点赞0 收藏0 评论

岱陌广场

P1063 能量项链 题解

题意简述

题目分析

Code

结语

绿【树形动态规划、DFS序】选课

题意概括

样例分析

题目分析

参考实现

复杂度分析

T1 题目

题目描述

输入格式

输出格式

数据范围

题解

40 分 DP / 完全背包做法

代码（完全背包写法）

复杂度

满分做法

分类讨论

情况1：n % 3 = 0

情况2：n % 3 = 1

情况3：n % 3 = 2

特殊情况

时间复杂度

T1 参考代码

T2 题目

题目描述

输入格式

输出格式

数据范围

T2 题解

T1 chip change

题目描述

输入格式

输出格式

样例

样例输入1:

样例输出1:

样例输入1:

样例输出2:

评分提示

参考代码

T2 COW

题目描述

平方串（square string）

操作

目标

参数 kkk 与操作次数要求

输入格式

输出格式

样例

样例输入1

样例输出1

样例解释1

语法A训练大纲

预备知识与符号约定

Bellman-Ford算法及其正确性证明

算法描述

正确性证明

1. 最短路径计算的正确性

2. 负权环路检测的正确性

划分DP

1、确定段数的划分\color{red}\text{1、确定段数的划分}1、确定段数的划分

1.定义状态\color{blue}\text{1.定义状态}1.定义状态

2. 状态转移方程\color{blue}\text{2. 状态转移方程}2. 状态转移方程

3. 初始化\color{blue}\text{3. 初始化}3. 初始化

4. 计算顺序\color{blue}\text{4. 计算顺序}4. 计算顺序

5. 答案提取\color{blue}\text{5. 答案提取}5. 答案提取

示例应用场景\color{blue}\text{示例应用场景}示例应用场景

2、不确定段数的划分\color{red}\text{2、不确定段数的划分}2、不确定段数的划分

1) 通用模板（枚举最后一段）\color{blue}\text{1) 通用模板（枚举最后一段）}1) 通用模板（枚举最后一段）

2) 常见目标类型与套路\color{blue}\text{2) 常见目标类型与套路}2) 常见目标类型与套路

A.\color{purple}A.A. 最小化“各段代价之和”

B.\color{purple}B.B. 最少段数（每段需“可行”）

C.\color{purple}C.C. 段数-代价联合权衡（拉格朗日/Alien’s Trick）

D.\color{purple}D.D. 最大化类（奖励可加）

P1063 能量项链题解

参数 $k$ 与操作次数要求

$\color{red}\text{1、确定段数的划分}$

$\color{blue}\text{1.定义状态}$

$\color{blue}\text{2. 状态转移方程}$

$\color{blue}\text{3. 初始化}$

$\color{blue}\text{4. 计算顺序}$

$\color{blue}\text{5. 答案提取}$

$\color{blue}\text{示例应用场景}$

$\color{red}\text{2、不确定段数的划分}$

$\color{blue}\text{1) 通用模板（枚举最后一段）}$

$\color{blue}\text{2) 常见目标类型与套路}$

$\color{purple}A.$ 最小化“各段代价之和”

$\color{purple}B.$ 最少段数（每段需“可行”）

$\color{purple}C.$ 段数-代价联合权衡（拉格朗日/Alien’s Trick）

$\color{purple}D.$ 最大化类（奖励可加）

$\color{blue}\text{3) 决策单调性与分治优化（可选）}$