二分图

发表于 2025-01-01 更新于 2026-01-07 分类于编程，算法，二分图本文字数： 367 阅读时长 ≈ 1 分钟

二分图

若一张无向图 $G$ ，可以将所有的点分成 $2$ 个点集，且 $2$ 个点集内部没有连边，那么称 $G$ 可以划分为一张二分图。

注意：二分图的划分不一定唯一，且不一定连通。有向图在实际问题中，也可以划分一分图

二分图存在的充要条件

没有奇环

二分图的判定

染色法，任意选择没有访问的点开始 dfs，并且 $0,1$ 交替染色，只要出现一条边的 $2$ 个端点颜色相同，那么就不是二分图。

阅读全文 »

区间dp

发表于 2025-01-01 更新于 2026-01-07 分类于编程，算法，动态规划，区间dp 本文字数： 1.7k 阅读时长 ≈ 6 分钟

区间DP

是一类子问题从短到长，而不是从左到右的动态规划问题。

状态

一般是： $dp_{i,j}$ 表示将区间 $[i,j]$ 的元素合并、拆分的最值、方案数。

转移

for (int len = 2; len <= n; len++)//这问题
	for (int i = 1; i + len - 1 <= n; i++)//状态
	{
		int j = i + len - 1;
		for (int k = i; k < j; k++)//决策点
		dp[i][j] = 运算(dp[i][j], 状态转移方程);
	}

阅读全文 »

区间dp（三）

发表于 2025-01-01 更新于 2026-01-07 分类于编程，算法，动态规划，区间dp 本文字数： 1.1k 阅读时长 ≈ 4 分钟

区间dp（三）

洛谷P1880

P1880 [NOI1995] 石子合并 - 洛谷

石子在圆形操场的四周摆放，直接当没有环形区间dp显然会少答案。那么我们一定要这么做怎么办？少了的话可以加回来，斩环为链，数组多一倍，再区间dp。

$dp_{0/1,i,j}$ 表示区间合并 $[i,j]$ 的最小/最大值。

答案为 $\displaystyle\min_{1\le i\lt n}^idp_{0,i,i+n-1}$ 和 $\displaystyle\max_{1\le i\lt n}^idp_{1,i,i+n-1}$ 。

$\displaystyle dp_{0,i,j}=\min_{i\le k\lt j}^k\left(dp_{0,i,k}+dp_{0,k+1,j}+\sum_{i\le l\le j}^la_l\right)$ ， $\displaystyle dp_{1,i,j}=\max_{i\le k\lt j}^k\left(dp_{1,i,k}+dp_{1,k+1,j}+\sum_{i\le l\le j}^la_l\right)$ 。