随便写写
tssys
·
·
个人记录
只要动态规划不在，我就是无敌的.png
本文讲述了一只新手写动态规划的思维与心得qwq.
二位数点优化dp,
二位数点
就是一个很常见的处理方式，可以使用树状数组来完成，比如求逆序对。
给一个长为 n 的序列，有 m 次查询，每次查区间 [l,r] 中值在
这个问题就叫做二维数点。我们可以发现等价于我们要查询一个二维平面上矩形内的点的数量和。这里讲一下这个问题最简单的处理方法，扫描线 + 树状数组。
很显然，这个问题是一个静态的二维问题，我们通过扫描线可以将静态的二维问题转换为动态的一维问题。维护动态的一维问题就使用数据结构维护序列，这里可以使用树状数组。
先将所有的询问离散化，用树状数组维护权值，对于每次询问的 $l$ 和 $r$，我们在枚举到 $l-1$ 时统计当前位于区间 $[x,y]$ 内的数的数量 𝑎
a，继续向后枚举，枚举到 𝑟
r 时统计当前位于区间 [𝑥,𝑦]
[x,y] 内的数的数量 b-a 即为该次询问的答案。
## 线段树优化dp
::::success[例题 [USACO25FEB] Friendship Editing G]{open}
{
### 题目背景
注意到本题特殊的时间限制。
[普通版](https://www.luogu.com.cn/problem/P8591)。
### 题目描述
给定 $n$ 条线段，第 $i$ 条是 $[l_i,r_i]$，将他们染成红色或黑色，要求：
1. 任意两条红色不相交
2. 任意一条黑色**至少**和一条红色相交。
请最小化红色线段的长度和，并输出这个长度和。
一条线段 $[l_i,r_i]$ 的长度定义为 $r_i-l_i$，两条线段 $[l_i,r_i],[l_j,r_j]$ 交**当且仅当**存在 $k\in[l_i,r_i]$ 且 $k\in[l_j,r_j]$。
### 输入格式
第一行一行一个正整数，代表 $n$。
接下来 $n$ 行，每行两个整数，代表 $l_i,r_i$，用空格隔开。
### 输出格式
一行一个非负整数，代表最小的红色线段的长度和。
### 输入输出样例 #1
#### 输入 #1
```
5
-6 5
1 3
-4 9
-1 10
6 8
```
#### 输出 #1
```
4
```
### 说明/提示
**数据范围**
|测试点编号|$n\le$|
| :----------: | :----------: |
|$1\sim10$|$5\times 10^5$|
对于所有数据，满足 $-10^9\le l_i<r_i\le10^9$。
本题采用捆绑测试。
}
::::
#### $n^2$ 如何
$n^2$ 怎么写呢，我们发现这个东西我们可以按照左端点排序或者右端点排序，不过个人认为除了贪心要按照 $r$ 排序其他的都要用 $l$，然后我们可以一个一个去处理，然后可以开一个虚点 0 也就是站位府，然后我们按照题意转移，如果相交就不转移，直到第一个可以转移的地方，然后我们一路扫，扫到一个点，看看他的右端点是不是大于最大的左端点，为什么呢，应为我们一是有顺序的，其次是如果再选的话就会漏掉。
注意这到题目中我们 $f_j$ 表示 **强制选 $i$** 的最小值，但是你不会求最小值怎么办，你只需要对于所有合法情况求min 就行了。
什么是合法的，你可以看看哪一个选完之后.就是当前的右端点包括了后面的点的所有左端点（在这道题里面）。
tags
1. **初始化**一个**虚拟节点**
2. **强制选i** 的方案数/最大值
3. **强制选i** 求答案是什么呢，是求所有**合法的最终状态**，从 $n$ 开始一步一步往前跳，直到不行。
4. **区间排序** 除了贪心就排第一关键字。
5. 对于任意一种如果**不选没有贡献**的情况，可以把它转化为 **强制选i**。
### 下一道题 https://www.luogu.com.cn/problem/CF777E
# 状态压缩dp,
状压 DP 是动态规划的一种，通过将状态集合转化为二进制记录在 DP 状态中来实现状态转移的目的。
为了达到更低的时间复杂度，通常需要寻找更低状态数的状态。大部分题目中会利用二元状态，用 $n$ 位二进制数表示 $n$ 个独立二元状态的情况。
使用状态压缩通常涉及位运算，关于基础位运算详见 [位运算](https://oi-wiki.org/math/bit/) 页面。
### 枚举所有子集
```cpp
for(int s=m;;s=(s-1)&m)
{
//s是m的一个子集
if(s==0)
break;
}
```
这个时间复杂度是 $O(3^n)$，具体证明可以去看看这篇文章 [戳](https://oi-wiki.org/math/binary-set/#%E9%81%8D%E5%8E%86%E6%89%80%E6%9C%89%E6%8E%A9%E7%A0%81%E7%9A%84%E5%AD%90%E6%8E%A9%E7%A0%81)。
::::success[例题 [USACO25FEB] Friendship Editing G]{open}
## 题目描述
Farmer John 的 $N$ 头奶牛编号为 $1$ 到 $N$（$2\le N\le 16$）。奶牛之间的朋友关系可以建模为一个有 $M$（$0\le M\le N(N-1)/2$）条边的无向图。两头奶牛为朋友当且仅当图中她们之间存在一条边。
在一次操作中，你可以添加或删除图中的一条边。计算确保以下性质成立所需的最小操作次数：保证该图的所有联通子图都是完全图。
## 输入格式
输入的第一行包含 $N$ 和 $M$。
以下 $M$ 行，每行包含一对朋友 $a$ 和 $b$（$1\le a<b\le N$）。每对朋友出现至多一次。
## 输出格式
输出你需要增加或删除的边的数量。
## 输入输出样例 #1
### 输入 #1
```
3 2
1 2
1 3
```
### 输出 #1
```
1
```
## 输入输出样例 #2
### 输入 #2
```
4 5
1 2
1 3
1 4
2 3
2 4
```
### 输出 #2
```
1
```
## 输入输出样例 #3
### 输入 #3
```
5 5
1 3
1 5
2 4
2 5
3 5
```
### 输出 #3
```
1
```
- 测试点 $4\sim 13$：对于每一个 $N\in [6, 15]$ 依次有一个测试点。
- 测试点 $14\sim 18$：$N=17$。
::::
看到这道题目，我们看到数据范围提示状压 DP，我们设 $f_s$ 表示当前只有 $s$ 这一类点合法的最小值。
$f_S=\min(f_T+G_{S/T})(T⊂S)$，$G_s$ 表示 $s$ 这个单独成团的最大值，然后就没了，因为要使用子集划分，所以时间复杂度为 $O(3^n+2^n\times n^2)$。