发表算法 / 动态规划10 分钟读完 (大约1483个字)

搜索与状压 DP

DFS

搜索和DP不分家，几乎所有的DP都能用搜索解决（虽然复杂度可能较劣）。不过，如果实在想不出正解，DFS不失为骗分的好手段。

主要的搜索算法有：

  1. DFS/BFS爆搜
  2. 双向BFS
  3. 启发式搜索（又称A*）
  4. 迭代加深搜索
  5. IDA*（迭代加深+启发式）
  6. 记忆化搜索
  7. 剪枝

重要程度：1,7,6 > 4,3 > 5,2。

阅读更多
发表算法 / 动态规划3 分钟读完 (大约411个字)

高级动态规划：区间、树形

区间 DP

P1880 [NOI1995]石子合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

const int N = 220;

int ans, dp[N][N], n, a[N], s[N];

int main() {
    
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) {
        scanf("%d", a+i);
        s[i] = s[i-1] + a[i];
    }
    for(int i=1; i<=n; ++i) {
        s[i+n] = s[i+n-1] + a[i];
    }
    memset(dp, 0x3f, sizeof dp);
    for(int i=1; i<=2*n; ++i) dp[i][i] = 0;
    for(int l=2; l<=n; ++l) {
        for(int i=1, j=l; j<=2*n; ++i, ++j) {
            for(int k=i; k<j; ++k) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]);
            }
        }
    }
    ans = 0x3f3f3f3f;
    for(int i=1; i<=n; ++i) {
        //printf("%d ", dp[i][i+n-1]);
        ans = min(ans, dp[i][i+n-1]);
    }
    printf("%d\n", ans);
    
    memset(dp, 0, sizeof dp);
    for(int i=1; i<=2*n; ++i) dp[i][i] = 0;
    for(int l=2; l<=n; ++l) {
        for(int i=1, j=l; j<=2*n; ++i, ++j) {
            for(int k=i; k<j; ++k) {
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]);
            }
        }
    }
    ans = 0;
    for(int i=1; i<=n; ++i) {
        ans = max(ans, dp[i][i+n-1]);
    }
    printf("%d\n", ans);
    return 0;
}

P1063 能量项链

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int N = 220;

int n, h[N], t[N], dp[N][N];
int main() {
    
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) {
        scanf("%d", &h[i]);
        h[i+n] = h[i];
    }
    for(int i=1; i<2*n; ++i) t[i] = h[i+1];
    
    for(int l=2; l<=n; ++l) {
        for(int i=1, j=l; j<=2*n; ++i, ++j) {
            for(int k=i; k<j; ++k) {
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + h[i] * t[k] * t[j]);
            }
        }
    }
    int ans = 0;
    for(int i=1; i<=n; ++i) {
        ans = max(ans, dp[i][i+n-1]);
    }
    printf("%d\n", ans);
    return 0;
}


P3146 [USACO16OPEN]248 G

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

int n, dp[300][300], ans = 0;
int main() {
    
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) {
        scanf("%d", &dp[i][i]);
    }
    
    for(int l=2; l<=n; ++l) {
        for(int i=1, j=l; j<=n; ++i, ++j){
            for(int k=i; k<j; ++k) {
                if(dp[i][k] == dp[k+1][j]) 
                    dp[i][j] = max(dp[i][j], dp[i][k]+1);
            }
            ans = max(ans, dp[i][j]);
        }
    } printf("%d\n", ans);
    return 0;
}

树形 DP

树形DP三大问题：树的最大独立集 树的重心 树的最长路径

阅读更多
C++ STL：SET & MULTISET
发表算法7 分钟读完 (大约982个字)

C++ STL：SET & MULTISET

定义

方式 效果
set <数据类型名> 集合名; 先定义一个容器，容器内无任何元素
set <数据类型名> 集合名(另一个集合名); 定义一个集合并用另一个集合初始化（只能是数据类型相同的集合，不能是数组）
set <数据类型名> 集合名(另一个集合名.begin(), 另一个集合名.end()); 定义一个集合并用另一个集合初始化（只能是数据类型相同的集合，不能是数组）
set <数据类型名> 集合名[集合数量]; 定义集合数组
set <Elem> 产生一个set，以 (operator <) 为排序准则
set <Elem, cmp> 产生一个set，以cmp为排序准则
阅读更多
数论：整除问题
发表算法 / 数论2 分钟读完 (大约361个字)

数论：整除问题

整除分块

与其说整除分块是一种算法，不如说它是一个技巧。有时我们需要计算这样的式子：

$$
\sum_{i=1}^n f(i)\lfloor\frac{n}{i}\rfloor
$$

根据经验，我们发现 $\lfloor\frac{n}{i}\rfloor$ 只有 $O(\sqrt n)$ 种取值。对于每种取值，$i$ 都会有一个连续的范围。假设函数 $f$ 的前缀和可以预处理后快速求出，那么我们可以枚举 $\lfloor\frac{n}{i}\rfloor$ 的所有取值，并和 $f$ 的连续一段的和相乘。具体可以见代码：

1
2
3
4
5
6
7
// s[i] 为函数 f(i) 的前缀和 
int ans = 0;
for(int i=1, j; i<=n; i=j+1) {
    j = n/(n/i);
    ans += (s[j]-s[i-1])*(n/i);
}
printf("%d\n", ans);
阅读更多
图论
发表算法13 分钟读完 (大约2024个字)

图论

图论算法一般都是揉在一起的，很难单独把算法拆开讲，所以直接上题目吧。分类是大致分的，其实有很多是交叉的。

二叉树

二叉树的遍历有三种，分别为前序遍历，中序遍历和后序遍历，并且给定其中的两种遍历能够求出另一种遍历 (必须已知中序遍历)。

阅读更多
还在用 STL 排序？
发表算法3 分钟读完 (大约495个字)

还在用 STL 排序？

使用 C 库函数

很多人都不知道的是，其实 C 语言也是自带排序函数的，就是位于 <stdlib.h> 库中的 qsort

函数声明：

阅读更多
网络流：最小割
发表算法 / 网络流18 分钟读完 (大约2681个字)

网络流：最小割

将图 $G$ 分为 $A$ 和 $B$ 两个点集，$A$ 和 $B$ 之间的边的集合称为无向图的割集。带权图的割 (Cut) 就是割集中的边权之和。

S - T 最小割

特别地，对于一个网络，在满足 $源点 s \in 点集{S}, 汇点 t \in 点集{T}(S\cap T= \varnothing)$ 的情况下，从 S 到 T 的边的权值和被称为 S 到 T 的割。

阅读更多
网络流：最大流
发表算法 / 网络流8 分钟读完 (大约1169个字)

网络流：最大流

EK

增广路方法是很多网络流算法的基础。其思路是每次找出一条从源到汇的能够增加流的路径，调整流值和残留网络 ，直到没有增广路为止。

EK 算法就是不断的找最短路，找的方法就是每次找一条边数最少的增广（即最短路径增广）。

最多要增广多少次？

可以证明，最多 O(VE)​ 次增广，可以达到最大流。

如何找到一条增广路？

先明确什么是增广路。增广路是一条从s到t的路径，路径上每条边残留容量都为正。把残留容量为正的边设为可行的边，那么我们就可以用简单的 BFS 得到边数最少的增广路。

阅读更多
关注我

分类

标签

AI2
Aplayer1
Butterfly1
DAG1
DFS3
GitHub1
Hexo2
LCA1
PB_DS1
SSH1
STL2
二分图2
动态规划3
匹配2
单调队列2
博客2
双指针1
图书馆4
图论4
小说7
尺取法1
平衡树1
排序2
数学1
数据结构1
数论3
最小割1
最短路4
树1
游记1
码风1
算法25
网络流5
记忆化搜索4
部署1
随感2
随笔1

最新文章

归档

×