首页 > 编程语言 >算法基础模板

算法基础模板

时间：2024-03-25 17:33:42浏览次数：22  
标签：... int 基础 times ++ 算法 include 模板 mod

目录

算法模版——基础篇

1、整数二分

bool check(int x){...}// 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1() // 二分查找1
{
    int l = 0, r = n - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2() // 二分查找2
{
    int l = 0, r = n - 1;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

2、浮点数二分

bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

3、高精度加法

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

4、高精度减法

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

5、高精度乘低精度

// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

6、高精度除以低精度

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

7、一维前缀和

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

8、二维前缀和

S[i, j] = 第i行j列格子左上部分所有元素的和
即 S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + a[i][j];
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

9、一维差分

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c;
void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

10、二维差分

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c;
void insert(int x1, int y1, int x2, int y2, int c)
{
    s[x1][y1] += c;
    s[x2 + 1][y1] -= c;
    s[x1][y2 + 1] -= c;
    s[x2 + 1][y2 + 1] += c;
}

11、位运算

求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

12、双指针算法

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

13、离散化

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

14、区间合并

// 将所有存在交集的区间合并, segs存区间的左右端点
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}

15、单链表

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

16、双链表

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

17、栈

// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0)
{

}

18、队列

1. 普通队列

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{

}

2. 循环队列

// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空，如果hh != tt，则表示不为空
if (hh != tt)
{

}

19、单调栈

常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

20、单调队列

常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

21、KMP

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

22、Tire树

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

23、并查集

(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);


(2)维护size的并查集：

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);


(3)维护到祖宗节点距离的并查集：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

24、字符串哈希

核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

25、拓扑排序

bool topsort()
{
    int hh = 0, tt = -1;

    // d[i] 存储点i的入度
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}

26、Dijkstra

朴素迪杰斯特拉

时间复杂度是 \(O(n^2+m)\)，\(n\) 表示点数，\(m\) 表示边数

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

堆优化版迪杰斯特拉

时间复杂度是 \(O(mlogn)\)，\(n\) 表示点数，\(m\) 表示边数

typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

27、Bellman-Ford算法

时间复杂度是 \(O(nm)\)，\(n\) 表示点数，\(m\) 表示边数

int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式
    // 就说明存在一条长度是n+1的最短路径
    // 由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

28、spfa算法

时间复杂度 平均情况下 \(O(m)\)，最坏情况下 \(O(nm)\) ， \(n\) 表示点数，\(m\) 表示边数

int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

29、floyd算法

时间复杂度是 \(O(n^3)\)，\(n\) 表示点数

初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

30、朴素版Prim算法

时间复杂度是 \(O(n^2 +m)\)，\(n\) 表示点数，\(m\) 表示边数

int n;      // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中


// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

31、Kruskal算法

时间复杂度是 \(O(mlogm)\)，\(n\) 表示点数，\(m\) 表示边数

int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组

struct Edge     // 存储边
{
    int a, b, w;

    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];

int find(int x)     // 并查集核心操作
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)     // 如果两个连通块不连通，则将这两个连通块合并
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}

32、染色法判断二分图

时间复杂度是 \(O(n + m)\)，\(n\) 表示点数，\(m\) 表示边数

int n;      // n表示点数
int h[N], e[M], ne[M], idx;     // 邻接表存储图
int color[N];       // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色

// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (color[j] == -1)
        {
            if (!dfs(j, !c)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

bool check()
{
    memset(color, -1, sizeof color);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (color[i] == -1)
            if (!dfs(i, 0))
            {
                flag = false;
                break;
            }
    return flag;
}

33、匈牙利算法

时间复杂度是 \(O(nm)\)，\(n\) 表示点数，\(m\) 表示边数

int n1, n2;     // n1表示第一个集合中的点数，n2表示第二个集合中的点数
// 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int h[N], e[M], ne[M], idx;     
int match[N];   // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];     // 表示第二个集合中的每个点是否已经被遍历过

bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
    memset(st, false, sizeof st);
    if (find(i)) res ++ ;
}

34、试除法判定质数

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}

35、试除法分解质因数

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

36、朴素筛法求素数（埃及筛）

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

37、线性筛法求素数（欧拉筛）

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

38、试除法求所有约数

vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}

39、约数个数和约数之和

如果 \(N = p_1^{c_1} \times p_2^{c_2} \times ... \times p_k^{c_k}\)

约数个数：\((c_1+1) \times (c_2 + 1) \times ... \times (c_k+1)\)

约数之和：\((p_1^0+p_1^1+...+p_1^{c_1})\times...\times (p_k^0+p_k^1+...+p_k^{c_k})\)

==>推公式约数之和：

\[(p_1^0+p_1^1+...+p_1^{c_1})\times...\times (p_k^0+p_k^1+...+p_k^{c_k}) \\ p_1^0+p_1^1+...+p_1^{c_1} \\ 令p_1 = p ,c_1=c\\ p^0+p^1+p^2+p^3+p^4+...+p^c \\ 1+p^1+p^2+p^3+p^4+...+p^c \\ 1+p^1(p^0+p^1+p^2+p^3+...+p^{c-1}) \\ 1+p^1(1+p^1(p^0+p^1+p^2+...+p^{c-2})) \\ 1+p^1(1+p^1(1+p^1(1+p^1(...))))\\ 相当于从内向外计算\\ 最里面的一定是1+p^1 \]

参考代码

/*约数个数*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;
    unordered_map<int, int> primes;
    // 分解质因数
    while (n -- )
    {
        int x;
        cin >> x;
        for(int i = 2; i <= x / i; i++)
            while(x % i == 0)
            {
                x /= i;
                primes[i]++;
            }
        if(x > 1) primes[x]++;
    }
    LL ans = 1;
    for(auto prime : primes)
    {
        ans = ans * (prime.second + 1) % mod;
    }
    cout << ans << endl;
    return 0;
}

/*约数之和*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;
    unordered_map<int, int> primes;
    // 分解质因数
    while (n -- )
    {
        int x;
        cin >> x;
        for(int i = 2; i <= x / i; i++)
            while(x % i == 0)
            {
                x /= i;
                primes[i]++;
            }
        if(x > 1) primes[x]++;
    }
    LL ans = 1;
    // 遍历每个质因数，存的是 p 和 c
    for(auto prime : primes)
    {
        int p = prime.first, c = prime.second;
        LL t = 1;
        while(c --) t = (t * p + 1) % mod;// 看公式的推导
        ans = ans * t % mod;
    }
    cout << ans << endl;
    return 0;
}

40、欧几里得算法

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

41、求欧拉函数

欧拉函数：对于正整数 \(n\) ，欧拉函数是小于等于 \(n\) 的正整数中与 \(n\) 互质的数的数目，记作 \(\varphi(n)\) 。特别的 \(\varphi(1)=1\)

求欧拉函数

首先欧拉函数是一个积性函数，当 \(m,n\) 互质时，\(\varphi(mn)=\varphi(m) \times \varphi(n)\)

根据唯一分解定理： \(n = p_1^{c_1} \times p_2^{c_2} \times ... \times p_k^{c_k}\)

因此：\(\varphi(n)=\varphi(p_1^{c_1}) \times ... \times \varphi(p_k^{c_k})\)

对于任意一项 \(\varphi(p_i^{c_i})=p_i^{c_i} - p_i^{c_i-1}\)

证明：

从 \(1\) 到 \(p_i^{c_i}\) 中共有 \(p_i^{c_i}\) 个数字

其中与 \(p_i^{c_i}\) 不互质的有 \(p_i,2p_i,3p_i,...,p_i\times p_i,...,p_i^{c_i-1}\times p_i\) 一共有 \(p_i^{c-1}\) 项

根据容斥原理 \(\varphi(p_i^{c_i})=p_i^{c_i} - p_i^{c_i-1}\)

所以把公式再化简：\(\varphi(p_i^{c_i})=p_i^{c_i} - p_i^{c_i-1}=p_i^{c_i}\times (1- \frac{1}{p_i})\)

所以：

\[\varphi(n)=\varphi(p_1^{c_1}) \times ... \times \varphi(p_k^{c_k})\\ =(p_1^{c_1}-p_1^{c_1-1}) \times ... \times (p_k^{c_k} - p_k^{c_k-1}) \\ =p_1^{c_1}\times (1- \frac{1}{p_1})\times p_2^{c_2}\times (1- \frac{1}{p_2}) \times ... \times p_k^{c_k}\times (1- \frac{1}{p_k})\\ =p_1^{c_1}\times p_2^{c_2}\times...\times p_k^{c_k}\times(1- \frac{1}{p_1})\times (1- \frac{1}{p_2})\times...\times(1- \frac{1}{p_k}) \\ =n\times \prod_{i=1}^k (1-\frac{1}{p_i}) \]

参考代码

/*求单个数的欧拉函数*/
int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}

/*求很多数的欧拉函数*/
int primes[N], cnt;     // primes[]存储所有素数
int phi[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉

void get_eulers(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                phi[t] = phi[i] * primes[j];
                break;
            }
            phi[t] = phi[i] * (primes[j] - 1);
        }
    }
}

代码理解：

  • 质数 \(i\) 的欧拉函数即为：phi[i] = i - 1; \(1\) ~ \(i-1\) 均与 \(i\) 互质，共 \(i - 1\) 个。
  • phi[primes[j] * i]分为两种情况：
    • i % primes[j] == 0：primes[j]是i的最小质因子，也是primes[j] * i的最小质因子，说明我们在算phi[i]的时候已经计算过 \(1-\frac{1}{primes[j]}\) 这一项了，即 \(\varphi(i)=i\times(1-\frac{1}{p_1})\times...\times (1-\frac{1}{p_k})\) ，并且 \(\varphi(i\times primes[j])=i\times primes[j] \times (1-\frac{1}{p_1})\times...\times (1-\frac{1}{p_k})\) ，所以 \(\varphi(i\times primes[j])=\varphi(i) \times primes[j]\) ，phi[primes[j] * i] = phi[i] * primes[j];
    • i % primes[j] != 0：primes[j]不是i的最小质因子，只是primes[j] * i的最小质因子，所以我们的 \(\varphi(i\times primes[j])=i\times primes[j] \times (1-\frac{1}{p_1})\times...\times (1-\frac{1}{p_k}) \times(1-\frac{1}{primes[j]})=\varphi(i) \times (primes[j] - 1)\)，phi[primes[j] * i] = phi[i] * (primes[j] - 1);

42、快速幂

求 \(m^k\text{mod}\ p\) ，时间复杂度 \(O(logk)\)

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k & 1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

43、扩展欧几里得算法

扩展欧几里得算法解决的问题：

  • 1、求解方程 \(ax+by=gcd(a,b)\) 的解

当 \(b=0\) 时， \(ax+by=a\) 故而 \(x=1,y=0\)

当 \(b \ne 0\) 时

因为

\[gcd(a,b)=gcd(b,a\%b) \]

原式可写为：

\[bx^{\prime}+(a\%b)y^{\prime}=gcd(b,a\%b)\\ bx^{\prime}+(a-\lfloor a \div b \rfloor \times b)y^{\prime}=gcd(b,a\%b)\\ ay^{\prime}+b(x^{\prime}-\lfloor a \div b \rfloor \times y^{\prime})=gcd(b,a\%b)=gcd(a,b) \]

与原式比较得：

\[x=y^{\prime},y=x^{\prime}-\lfloor a \div b \rfloor \times y^{\prime} \]

因此可以采取递归算法，先求出下一层的 \(x^{\prime}\) 和 \(y^{\prime}\) 再利用上述公式回代即可。

  • 2、求解更一般的方程 \(ax+by=c\)

我们可以设 \(d=gcd(a,b)\) 则这个方程有解的条件是：当且仅当 \(d \mid c\) 即 \(d\) 整除 \(c\) \((c \mod d = 0)\)

求解：

用扩展欧几里得求出 \(ax_0+by_0=d\) 的解

则同时扩大 \(\frac{c}{d}\) 倍： \(a(x_0 \times c/d)+b(y_0 \times c/d)=c\)

故而一个特解为：\(x^{\prime}=x_0 \times c/d, \ y^{\prime}=y_0 \times c/d\)

我们知道：非齐次方程的通解 = 非齐次方程的一个特解 + 齐次方程的通解

所以下一步求齐次方程：\(ax+by=0\) 的通解

\[ax+by=0\\ ax=-by\\ x=-\frac{b}{a}y\\ 设d=gcd(a,b)\\ \because a=a_1\times d\ ,b=b_1\times d\\ \therefore gcd(a_1,b_1)=1\\ x=-\frac{b_1\times d}{a_1\times d}y\\ x=-\frac{b_1}{a_1}y\\ \because a_1,b_1互质，则x有整数解\\ a_1 \mid y=>y=k \times a_1=>y=k\times \frac{a}{d}(k\in z)\\ \therefore 带入y得x=-k\frac{b}{d}\\ 同理y=x\times -\frac{a}{b}=k\frac{a}{d} \]

所以非齐次方程的通解为：

\[x=x^{\prime}-k\frac{b}{d},y=y^{\prime}+k\frac{a}{d},k\in z\\ 当然k\frac{b}{d}前面的符号只需要保证在x和y的表达式中是相反的就可以 \]

若令 \(t=b/d\) ，则对于 \(x\) 的最小非负整数解为 \((x^{\prime}\%t+t)\%t\)

  • 3、求解一次同余方程 \(ax\equiv b(mod\ m)\)

等价于求：

\[ax=m\times (-y)+b\\ ax+my=b \]

有解条件为：\(gcd(a,m) \mid b\) ，然后用扩展欧几里得求解即可

特别的 当 \(b=1\) 且 \(a\) 与 \(m\) 互质时，所求的 \(x\) 即为 \(a\) 的逆元

扩展欧几里得参考代码

/*模版一*/
int exgcd(int a, int b, int &x, int &y) // 返回值为最大公约数
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int x1, y1, d;
    d = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - a / b * y1;
    return d;
}
/*模版二*/
int exgcd(int a, int b, int &x, int &y) // 返回值为最大公约数
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

44、逆元

乘法逆元的定义：若整数 \(b,m\) 互质， 并且对于任意整数 \(a\) ，如果满足 \(b \mid a\) ，则存在一个 \(x\) ，使得 \(a \times b^{-1} \equiv a\times x(\text{mod}\ m)\) ，则称 \(x\) 为 \(b\) 的模 \(m\) 的乘法逆元，记为 \(b^{-1}(\text{mod}\ m)\)。

1. 快速幂求逆元(m为质数)

推公式：

\[a\times b^{-1} \equiv a\times x(\text{mod} \ m)\\ 两边同时乘b得： a \equiv a \times b \times x(\text{mod} \ m)\\ 即 1\equiv b \times x(\text{mod} \ m)\\ 同 b \times x \equiv 1(\text{mod} \ m)\\ 由费马小定理可知，当m为质数时：\\ b^{m-1}\equiv 1(\text{mod} \ m)\\ 拆一个b出来\\ b\times b^{m -2}\equiv 1(\text{mod} \ m)\\ 对比上式得到 x=b^{m-2} \]

所以当 \(m\) 为质数时，\(b\) 的乘法逆元 \(x=b^{m-2}(\text{mod} \ m)\) ，直接使用快速幂 qmi(b, m - 2, m)

2、扩展欧几里得算法求逆元

前提：\(a\) 有逆元的充要条件是 \(a\) 与 \(m\) 互质，所以有 \(gcd(a,m)=1\)

假设 \(a\) 的逆元为 \(x\) ，那么有 \(a\times x \equiv 1(\text{mod}\ m)\)

等价：\(ax+my=1\) 直接使用扩展欧几里得算法 exgcd(a, m, x, y)

如何保证求得的 \(x\) 为正数？ cout<<(x + m) % m

3、欧拉定理求逆元

欧拉定理：设 \(m,a\in N^+\) ，且 \(gcd(a,m)=1\) ，则我们有 \(a^{\varphi(m)}\equiv1(\text{mod}\ m)\) ，\(\varphi(m)\) 为 \(m\) 的欧拉函数

对上式定理进行变形得： \(a \times a^{\varphi(m)-1}\equiv1(\text{mod}\ m)\)

所以令 \(a\) 的逆元是 \(a^{-1}\) 即 \(a^{-1}= a^{\varphi(m)-1}(\text{mod}\ m)\)

4、线性求逆元

有时候我们不一定是只求单个的逆元，需要求很多数的逆元，如果每次都用1、2、3方法复杂度就非常大了。

在线性时间复杂度求出 \([1,n]\) 在模 \(p\) 意义下的逆元（ \(p\) 必须是质数）

首先从 \(p\) 入手， \(p \div i=q\cdots r\) （其中 \(q\) 是商， \(r\) 是余数），移项得： \(p=q\times i+r\)

模上 \(p\) 得：\(0=q\times i+r(\text{mod}\ p)\)

左右两边同时乘上 \(i^{-1}\times r^{-1}\) 得： \(0=q\times r^{-1} + i^{-1}(\text{mod}\ p)\)

移项得：\(i^{-1}=-q\times r^{-1}(\text{mod}\ p)\)

又因为 \(q=\lfloor \frac{p}{i} \rfloor\) ，\(r=p\ \text{mod}\ i\) 带入上式得

\[i^{-1}=-\lfloor \frac{p}{i} \rfloor \times (p\ \text{mod}\ i)^{-1}(\text{mod}\ p)\\ i^{-1}=(-\lfloor \frac{p}{i} \rfloor \times (p\ \text{mod}\ i)^{-1}+p\times (p\ \text{mod}\ i)^{-1})(\text{mod}\ p)\\ 为什么可以加p\times (p\ \text{mod}\ i)^{-1}\\ 因为在模p的意义下p\times (p\ \text{mod}\ i)^{-1}为0\\ \therefore i^{-1}=(p-\lfloor \frac{p}{i} \rfloor) \times (p\ \text{mod}\ i)^{-1}(\text{mod}\ p) \]

用代码写成递推表达式：inv[i] = (p - p / i) * inv[p % i] % p; 初始值：inv[0] = inv[1] = 1;

LL inv[N];

void mod_inverse(LL n, LL p)
{
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = (p - p / i) * inv[p % i] % p;
}

45、中国剩余定理

定理内容：给定一系列两两互质的数 \(m_1,m_2,m_3,...,m_k\) ，解决一个线性同余方程组：

\[\begin{cases} x\equiv a_1(\text{mod}\ m_1)\\ x\equiv a_2(\text{mod}\ m_2)\\ x\equiv a_3(\text{mod}\ m_3)\\ ...\\ x\equiv a_k(\text{mod}\ m_k)\\ \end{cases} \]

有一个公式解：

\[x=a_1\times M_1 \times M_1^{-1} + a_2\times M_2 \times M_2^{-1} +... + a_k\times M_k \times M_k^{-1} \]

其中 \(M=m_1\times m_2 \times ... \times m_k\) ， \(M_i=\frac{M}{m_i}\) ， \(M_i^{-1}\) 表示 \(M_i\) 模 \(m_i\) 的逆

46、高斯消元法

// a[N][N]是增广矩阵
int gauss()
{
    int c, r;
    for (c = 0, r = 0; c < n; c ++ )
    {
        int t = r;
        for (int i = r; i < n; i ++ )   // 找到绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;

        if (fabs(a[t][c]) < eps) continue;

        for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);// 将绝对值最大的行换到最顶端
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];// 将当前行的首位变成1
        for (int i = r + 1; i < n; i ++ ) // 用当前行将下面所有的列消成0
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;
    }

    if (r < n)
    {
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps)
                return 2; // 无解
        return 1; // 有无穷多组解
    }

    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[i][j] * a[j][n];

    return 0; // 有唯一解
}

// 输出
int t = gauss();
    
if (t == 0)
{
    for (int i = 0; i < n; i++) printf("%.2lf\n", a[i][n]);
}
else if (t == 1) puts("Infinite group solutions");
else puts("No solution");

47、求组合数

组合数

\[C_a^b=\frac{a!}{(a-b)!b!} \]

1. 递推法求组合数

// c[a][b] 组合数
for (int i = 0; i < N; i ++ )
    for (int j = 0; j <= i; j ++ )
        if (!j) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

2. 预处理逆元的方式求组合数

首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
如果取模的数是质数，可以用费马小定理求逆元
int qmi(int a, int k, int p)    // 快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
    fact[i] = (LL)fact[i - 1] * i % mod;
    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}

// 输出 C[a,b] = a! / ((a - b)! * b!)
cout << (LL)fact[a] * infact[a - b] % mod * infact[b] % mod << endl;

3. Lucas定理求组合数

卢卡斯定理： \(C_a^b \equiv C_{a\mod p}^{b \mod p} * C_{a/p}^{b/p} (mod \ p)\)

若p是质数，则对于任意整数 1 <= m <= n，有：
    C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)

int qmi(int a, int k, int p)  // 快速幂模板
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int C(int a, int b, int p)  // 通过定理求组合数C(a, b)
{
    if (a < b) return 0;

    LL x = 1, y = 1;  // x是分子，y是分母
    for (int i = a, j = 1; j <= b; i --, j ++ )
    {
        x = (LL)x * i % p;
        y = (LL) y * j % p;
    }

    return x * (LL)qmi(y, p - 2, p) % p;
}

int lucas(LL a, LL b, int p)
{
    if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

48、01背包

01背包问题：有 \(N\) 件物品和一个容量为 \(V\) 的背包，每件物品有各自的价值且只能被选择一次，要求在有限的背包容量下，装入的物品总价值最大。

解决动态规划问题的方法和步骤：

  • 状态定义：f[i][j]表示前 \(i\) 个物品，背包容量 \(j\) 下的最优解（最大价值）
  • 状态含义：最大值（max）
  • 状态计算：
    • 当背包容量不够时j < v[i]：不能选了，f[i][j] = f[i - 1][j]
    • 当背包容量充足j >= v[i]：可以选这个物品，可以不选这个物品，但是我们求最大的价值，f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])

image-20231211154040763

#include <iostream>

using namespace std;

const int N = 1005;
int f[N];
int n, m;
int v[N], w[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        
    cout << f[m] << endl;
}

49、完全背包

完全背包问题：有 \(N\) 件物品和一个容量为 \(V\) 的背包，每件物品有各自的价值并且有无数件可用，要求在有限的背包容量下，装入的物品总价值最大。

状态表示和01背包一样，只是状态计算有变化。

第 \(i\) 个物品可以选择 \(0,1,2,...,k,...\) 个，只要在背包容量足够的时候。

f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - 2*v] + 2*w, ... )

f[i][j - v] = max( f[i - 1][j - v] , f[i - 1][j - 2*v] + w, ... )

观察上式，可以用 f[i][j - v] + w 代替 f[i - 1][j - v] + w, f[i - 1][j - 2*v] + 2*w, ... 所以最后的状态转移方程就是

f[i][j] = max(f[i - 1][j], f[i][j - v] + w)

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++)
        for(int j = v[i]; j <= m; j++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);


    cout << f[m] << endl;

    return 0;
}

50、多重背包

多重背包问题：有 \(N\) 件物品和一个容量为 \(V\) 的背包，第 \(i\) 种物品最多有 \(s_i\) 件，每件体积是 \(v_i\) ，价值是 \(w_i\)，要求在有限的背包容量下，装入的物品总价值最大。

朴素的多重背包

分析：

  • 当 \(s =1\) 时，可以认为是 01 背包问题。
  • 当 \(s\gt 1\) 时，相当于 01 背包中的多个一件物品

f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - 2*v] + 2*w, ..., f[i - 1][j - k*v] + k*w)

所以我们还需要用一个循环找使得价值最大的 \(k\)

#include <iostream>

using namespace std;

const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];

    for(int i = 1; i <= n; i++)
        for(int j = m; j >= v[i]; j--)
            for(int k = 0; k <= s[i] && k * v[i] <= j; k++)
                f[j] = max(f[j], f[j - v[i] * k] + k * w[i]);

    cout << f[m] << endl;

    return 0;
}

二进制优化的多重背包

我们发现，朴素做法会有3层循环，前面的两层循环我们是固定的，我们从枚举 \(k\) 入手，朴素做法是最多枚举 \(k\) 次，时间复杂度是 \(O(k)\) 。

我们知道，任何一个数，我们可以拆成所有类似 \(2^02^12^2...\) 之类的加起来，所以我们想到二进制的方法枚举 \(k\) ，那么时间复杂度就变为 \(O(log\ k)\)

比如有40个苹果，我们要拿40个，朴素做法就是一个一个拿，但是用二进制的方法把40分成 \(1,2,4,8,16,9\) 六堆，我们只需要拿6次。

#include <iostream>

using namespace std;

const int N = 24000, M = 2010;
int n, m;
int v[N], w[N];
int f[M];

int main()
{
    cin >> n >> m;
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        int a, b, s;
        cin >> a >> b >> c;
        for (int k = 1; k <= s; k *= 2)
        {
            cnt++;
            v[cnt] = a * k, w[cnt] = b * k;
            s -= k;
        }
        if (s > 0)
        {
            cnt++;
            v[cnt] = a * s, w[cnt] = b * s;
        }
    }
	
    n = cnt; // 重新赋值n
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

单调队列优化的多重背包

我们注意到，当数据量为 \(10^{4}\) 时，二进制优化也会 TLE。所以我们使用单调队列来优化。

多重背包原始状态转移方程

\[f(i,j)=\max(f(i-1,j),f(i-1,j-v)+w,...,f(i-1,j-sv)+sw) \]

考虑使用完全背包的优化方式优化

\[f(i,j-v)=\max(f(i-1,j-v),f(i-1,j-2v)+w,...,+f(i-1,j-(s+1)v)+sw) \]

继续推下去 我们令 \(r = j \mod v_i\)

\[\begin{cases} f(i,j)=\max(f(i-1,j),f(i-1,j-v)+w,...,f(i-1,j-sv)+sw)\\ f(i,j-v)=\max(f(i-1,j-v),f(i-1,j-2v)+2w,...,f(i-1,j-(s+1)v)+sw)\\ f(i,j-2v)=\max(f(i-1,j-2v),f(i-1,j-3v)+w,...,f(i-1,j-(s+2)v)+sw)\\ ...\\ f(i,r+sv)=\max(f(i-1,r+sv),f(i-1,r+(s-1)v)+w,...,f(i-1,r)+sw)\\ f(i,r+(s-1)v)=\max(f(i-1,r+(s-1)v),f(i-1,r+(s-2)v)+w,...,f(i-1,r)+(s-1)w)\\ f(i,r+(s-2)v)=\max(f(i-1,r+(s-2)v),f(i-1,r+(s-3)v)+w,...,f(i-1,r)+(s-2)w)\\ ...\\ f(i,r+2v)=\max(f(i-1,r+2v),f(i-1,r+v)+w,f(i-1,r)+2w)\\ f(i,r+v)=\max(f(i-1,r+v),f(i-1,r)+w)\\ f(i,r)=f(i-1,r) \end{cases} \]

我们从下往上看，可以发现是一个滑动窗口求最值的问题。窗口长度恰好是 \(s\) 即物品数量，结合下图了解：

image-20231211154040763

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20010;

int n, m;
int f[N], g[N], q[N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        memcpy(g, f, sizeof f);
        for (int r = 0; r < v; r++)
        {
            int hh = 0, tt = -1;
            for (int k = r; k <= m; k += v)
            {
                if (hh <= tt && q[hh] < k - s * v) hh ++;
                if (hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w);
                while (hh <= tt && g[q[tt]] - (q[tt] - r) / v * w <= g[k] - (k - r) / v * w) tt --;
                q[ ++ tt] = k;
            }      
        }
    }
    cout << f[m] << endl;
    return 0;
}

51、分组背包

分组背包问题：有 \(N\) 件物品和一个容量为 \(V\) 的背包，每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 \(v_{ij}\) ，价值是 \(w_{ij}\) ，其中 \(i\) 是组号，\(j\) 是组内编号。求解将那些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输入格式

第一行有两个整数 \(N\) ，\(V\) ，用空格隔开，分别表示物品组数和背包容量

接下来有 \(N\) 组数据：

  • 每组数据的第一行有一个整数 \(S_i\) ，表示第 \(i\) 个物品组的物品数量
  • 每组数据接下来有 \(S_i\) 行，每行有两个整数 \(v_{ij}\) ，\(w_{ij}\) ，用空格隔开，分别表示第 \(i\) 个物品组的第 \(j\) 个物品的体积和价值

这道题和01背包类似

  • 对于每组 \(s\) 个物品，我们有 \(s+1\) 种选法：\(f(i,j)=\max(f(i-1,j),f(i-1,j-v_0)+w_0,f(i-1,j-v_1)+w_1),...,f(i-1,j-v_s)+w_s)\) 就是s说可以不选、选一个、选两个、…、选 \(s\) 个。
  • 所以我们先循环枚举所有体积，再循环枚举所有选择，最后得出状态转移方程：\(f(i,j)=\max(f(i-1,j),f(i-1,j-v_k)+w_k)\) ，其中 \(k\) 是枚举所有选择种的循环变量。
#include <iostream>

using namespace std;

const int N = 105;
int v[N][N], w[N][N], s[N];
int n, m;
int f[N];

int main()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i ++)
    {
        cin >> s[i];
        for(int j = 0; j < s[i]; j ++)
        {
            cin >> v[i][j] >> w[i][j];
        }
    }

    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 0; j--)
            for(int k = 0; k <= s[i]; k++)
                if(v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

    cout << f[m] << endl;

    return 0;
}

52、线性DP

数字三角形

#include <iostream>

using namespace std;

const int N = 505, INF = 1e9;

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

int main()
{
    cin >> n;
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            cin >> a[i][j];
    
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= i + 1; j++)
            dp[i][j] = -INF;
    
    dp[1][1] = a[1][1];
    
    for(int i = 2; i <= n; i++)
        for(int j = 1; j <= i; j++)
            dp[i][j] = max(dp[i - 1][j] + a[i][j], dp[i - 1][j - 1] + a[i][j]);

    ans = -INF;
    
    for(int i = 1; i <= n; i++) ans = max(ans, dp[n][i]);
        
    cout << ans;
    return 0;
}

最长上升子序列（朴素）

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int a[N], f[N];
int n;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    for(int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for(int j = 1; j < i; j++)
            if(a[j] < a[i]) // 如果是下降，变成大于即可
                f[i] = max(f[i], f[j] + 1);
    }

    int res = 0;
    for(int i = 1; i <= n; i++) res = max(res, f[i]);

    printf("%d\n",res);

    return 0;
}

最长上升子序列（二分优化）

这是一个贪心思想，找出来的vector序列不一定是我们所求的上升子序列，但是个数肯定是对的。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;
int a[N];
int n;
vector<int> q;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    q.push_back(a[0]);

    for (int i = 1; i < n; i++)
    {
        if (a[i] > q.back()) q.push_back(a[i]);
        else *lower_bound(q.begin(), q.end(), a[i]) = a[i];
    }

    cout << q.size() << endl;


    return 0;
}
/*
lower_bound(q.begin(), q.end(), a[i]) 返回找到第一个大于等于a[i]的值的迭代器位置，解引用后是值
*/

最长公共子序列

状态定义：f[i][j] 表示在第一个序列的前 \(i\) 个字母中出现并且在第二个序列的前 \(j\) 个字母中出现的最大值

以第 \(i\) 个字母是否相同来划分。

28466_6610da5048-问题分析

如果两个字符相等，就可以直接转移到 f[i - 1][j - 1]，不相等的话，两个字符一定有一个可以抛弃，可以对 f[i - 1][j],f[i][j - 1] 两种状态取max来转移。

#include <iostream>

using namespace std;

const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    cin >> a + 1 >> b + 1; // 下标从1开始

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            f[i][j] = max(f[i - 1][j] , f[i][j - 1]);
            if(a[i] == b[j]) 
            {
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
            }
        }
    cout << f[n][m] << endl;
    return 0;
}

最短编辑距离

状态表示：f[i][j] 表示将 a[i] 变为 b[j] 的操作方式，属性 min

状态计算：

有三种操作，所以有三个子集
ok子集划分完了
考虑状态转移的时候
先考虑如果我没有进行这个操作应该是什么状态
然后考虑你进行这一步操作之后会对你下一个状态造成什么影响
然后再加上之前状态表示中你决策出来的那个DP属性
这样就可以自然而然地搞出来转移方程啦

1)删除操作：把a[i]删掉之后a[1~i]和b[1~j]匹配
            所以之前要先做到a[1~(i-1)]和b[1~j]匹配
            f[i-1][j] + 1
2)插入操作：插入之后a[i]与b[j]完全匹配，所以插入的就是b[j] 
            那填之前a[1~i]和b[1~(j-1)]匹配
            f[i][j-1] + 1 
3)替换操作：把a[i]改成b[j]之后想要a[1~i]与b[1~j]匹配 
            那么修改这一位之前，a[1~(i-1)]应该与b[1~(j-1)]匹配
            f[i-1][j-1] + 1
            但是如果本来a[i]与b[j]这一位上就相等，那么不用改，即
            f[i-1][j-1] + 0

好的那么f[i][j]就由以上三个可能状态转移过来，取个min

细节问题：初始化怎么搞
先考虑有哪些初始化嘛
1.你看看在for遍历的时候需要用到的但是你事先没有的
（往往就是什么0啊1啊之类的）就要预处理 
2.如果要找min的话别忘了INF
  要找有负数的max的话别忘了-INF

ok对应的： 
1.f[0][i]如果a初始长度就是0，那么只能用插入操作让它变成b
  f[i][0]同样地，如果b的长度是0，那么a只能用删除操作让它变成b
2.f[i][j] = INF //虽说这里没有用到，但是把考虑到的边界都写上还是保险

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    cin >> n >> a + 1 >> m >> b + 1;
    // 边界情况，a没有只能是a增加，b没有只能是a删除
    for (int i = 0; i <= m; i++) f[0][i] = i; 
    for (int i = 0; i <= n; i++) f[i][0] = i;
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1); // 删除或插入取其一最小
            if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]); // 和相等取min
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1); // 和不等取min
        }
        
    cout << f[n][m] << endl;
    
    return 0;
}

编辑距离

给定 \(n\) 个长度不超过 \(10\) 的字符串以及 \(m\) 次询问，每次询问给出一个字符串和一个操作次数上限。

对于每次询问，请你求出给定的 \(n\) 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

image-20231213152110209

image-20231213152124492

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15, M = 1010;

int n, m;
char str[M][N];
int f[N][N];

int check(char a[], char b[])
{
    int la = strlen(a + 1);
    int lb = strlen(b + 1);
    
    for (int i = 0; i <= lb; i++) f[0][i] = i;
    for (int i = 0; i <= la; i++) f[i][0] = i;
    
    for (int i = 1; i <= la; i++)
        for (int j = 1; j <= lb; j++)
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }
        
    return f[la][lb];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> str[i] + 1;
    while (m -- )
    {
        char a[N];
        int limit;
        cin >> a + 1 >> limit; 
        int res = 0;
        for (int i = 1; i <= n; i++)
            if (check(str[i], a) <= limit) 
                res ++;
                
        cout << res << endl;
    }
    return 0;
}

53、区间DP

例题：石子合并，合并 \(N\) 堆石子，每次只能合并相邻的两堆石子，求最小代价

解题思路：最后一次合并一定是左边连续的一部分和右边连续的一部分进行合并

状态表示：f[i][j] 表示将 \(i\) 到 \(j\) 这一段石子合并成一堆的方案的集合，属性：min

状态计算：

  • \(i \lt j\) 时，\(f[i][j]=\min\limits_{i\le k\le j-1}(f[i][k]+j[k+1][j]+s[j]-s[i-1])\)
  • \(i=j\) 时，\(f[i][i]=0\) （合并一堆石子的代价为0）

问题答案：\(f[1][n]\)

常见的区间DP思路：所有的区间dp问题枚举时，第一维通常是枚举区间长度，并且一般 \(len = 1\) 时用来初始化，枚举从 \(len = 2\) 开始；第二维枚举起点 \(i\) （右端点 \(j\) 自动获得，\(j = i + len - 1\)）；第三维枚举决策

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310;

int f[N][N];
int s[N];
int n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1];
    
    for (int len = 2; len <= n; len ++)
        for (int i = 1; i + len - 1 <= n; i++)
        {
            int l = i, r = i + len - 1;
            f[l][r] = 1e8;
            for (int k = l; k < r; k++)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }
    
    cout << f[1][n] << endl;
    return 0;
}

54、计数DP

例题：一个正整数 \(n\) 可以表示成若干个正整数之和，形如：\(n=n_1+n_2+...+n_k\) 其中 \(n_1\ge n_2 \ge ... \ge n_k,k \ge1\) 。我们将这样的一种表示称为正整数 \(n\) 的一种划分，现在给定一个正整数 \(n\) ，请你求出 \(n\) 有多少种不同的划分方法。

使用完全背包的思想：把 \(1,2,3, … n\) 分别看做 \(n\) 个物体的体积，这 \(n\) 个物体均无使用次数限制，问恰好能装满总体积为 \(n\) 的背包的总方案数（完全背包问题变形）

#include <iostream>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N];

int main()
{
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            f[j] = (f[j] + f[j - i]) % mod;
        
    cout << f[n] << endl;
    return 0;
}

55、状态压缩DP

棋盘式类问题

例题：蒙德里安的梦想，求把 \(N \times M\) 的棋盘分割成若干个 \(1 \times 2\) 的长方形，有多少种方案。

核心思路：

  1. 题目分析

  • 将分割变为摆放若干个 \(1 \times 2\) 的长方形。

  • 摆放方块的时候，先放横着的，再放竖着的。总方案数等于只放横着的小方块的合法方案数。

  • 如何判断，当前方案数是否合法？ 所有剩余位置能否填充满竖着的小方块。可以按列来看，每一列内部所有连续的空着的小方块需要是偶数个。

  • 这是一道动态规划的题目，并且是一道 状态压缩的dp：用一个 \(N\) 位的二进制数，每一位表示一个物品，0/1表示不同的状态。因此可以用 \(0\rightarrow2^N-1(N:二进制对应的十进制数)\) 中的所有数来枚举全部的状态。

  1. 状态表示

状态表示：\(f[i][j]\) 表示已经将前 \(i - 1\) 列摆好了，且从第 \(i - 1\) 列，伸出到第 \(i\) 列的状态是 \(j\) 的所有方案，其中\(j\) 是个二进制数，用来表示哪一行的小方块是横着放的，其位数和棋盘的行数一致

  1. 状态转移

  • 既然第 \(i\) 列固定了，我们需要看 第 \(i-2\) 列是怎么转移到到第 \(i-1\)列的（看最后转移过来的状态）。假设此时对应的状态是 \(k\)（第 \(i-2\) 列到第 \(i-1\) 列伸出来的二进制数，比如 \(00100\) ），\(k\) 也是一个二进制数，\(1\)表示哪几行小方块是横着伸出来的，\(0\)表示哪几行不是横着伸出来的。

  • 它对应的方案数是 \(f[i-1][k]\) ，即前 \(i-2\) 列都已经摆完，且从第 \(i - 2\) 列伸到第 \(i-1\) 列的状态为 \(k\) 的所有方案数。

  • 这个 \(k\) 需要满足什么条件呢？

  • 首先 \(k\) 不能和 \(j\) 在同一行，因为从 \(i-1\)列到第 \(i\) 列是横着摆放的\(1\times2\)的方块，那么 \(i-2\) 列到 \(i-1\) 列就不能是横着摆放的，否则就是\(1\times3\)的方块了！这与题意矛盾。所以 \(k\) 和 \(j\) 不能位于同一行。

  • 既然不能同一行伸出来，那么对应的代码为(k & j) == 0，表示两个数相与，\(k\) 和 \(j\) 没有一位相同，即没有1行有冲突。

  • 既然从第 \(i-1\) 列到第 \(i\) 列横着摆的，和第 \(i-2\) 列到第 \(i-1\) 列横着摆的都确定了，那么第 \(i-1\) 列 空着的格子就确定了，这些空着的格子将来用作竖着放。如果某一列有这些空着的位置，那么该列所有连续的空着的位置长度必须是偶数。

  • 总共 \(m\) 列，我们假设列下标从0开始，即第0列，第1列……，第 \(m-1\)列。根据状态表示 \(f[i] [j]\) 的定义，我们答案是什么呢？ 答案是 \(f[m][0]\)， 意思是前 \(m-1\) 列全部摆好,且从第 \(m-1\) 列到 \(m\) 列状态是0（意即从第 \(m-1\) 列到第 \(m\) 列没有伸出来的）的所有方案，即整个棋盘全部摆好的方案。

时间复杂度：\(O(n\times2^n\times2^n)=11\times2^{11}\times2^{11}≈4\times10^7\)

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 12, M = 1 << N;

long long f[N][M];
bool st[M];
vector<int> state[M];

int main()
{
    int n, m;
    while (cin >> n >> m , n || m)
    {
        for (int i = 0; i < 1 << n; i ++ )
        {
            int cnt = 0;
            st[i] = true;
            for (int j = 0; j < n; j ++ )
                if (i >> j & 1)
                {
                    if (cnt & 1) st[i] = false;
                    cnt = 0;
                }
                else cnt ++ ;
            if (cnt & 1) st[i] = false;
        }

        for (int i = 0; i < 1 << n; i++)
        {
            state[i].clear();
            for (int j = 0; j < 1 << n; j++)
            {
                if ((i & j) == 0 && st[i | j])
                    state[i].push_back(j);
            }
        }

        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for (int i = 1; i <= m; i ++ )
            for (int j = 0; j < 1 << n; j ++ )
                for (auto t : state[j])
                    f[i][j] += f[i - 1][t];

        cout << f[m][0] << endl;
    }
    return 0;
}

集合类问题

例题：最短Hamilton路径，给定一张 \(n\) 个点的带权无向图，点从 \(0\) 到 \(n-1\) 标号，求起点 \(0\) 到终点 \(n-1\) 的最短Hamilton路径。 Hamilton路径的定义是从 \(0\) 到 \(n-1\) 不重不漏地经过每个点恰好一次。输入的是一张图。

/*输入*/
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
/*输出*/
18

DP分析

用二进制来表示要走的所以情况的路径,这里用 \(i\) 来代替

例如走 \(0,1,2,4\) 这四个点，则表示为: \(10111\) ；走 \(0,2,3\) 这三个点，则表示为： \(1101\)

状态表示：f[i][j] 表示所有从 \(0\) 走到 \(j\) ，走过的所有点的情况是 \(i\) 的所有路径，属性：min

状态计算：f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]) 或者 f[i][j] = min(f[i][j], f[i ^ (1 << j)][k] + w[k][j]) 考虑所有 \(k\) 的情况，计算从 \(k\) 到 \(j\) 的这段路程，减号和异或符号效果一样。

注意为什么是 i - (1 << j) 因为我们的 \(i\) 表示的是一类集合，比如说 \(i=13\) 用二进制表示为：\(1101\) 相当于走过了 \(0、2、3\) 号点，如果 \(j=2\) 那么 i - (1 << j) 的计算结果为 \(9\) 用二进制表示为：\(1001\) 可以看到是不是 \(2\) 号点就剔除了，所以我们的意思就是从走过的 \(0、3\) 号点转移到未走过的 \(2\) 号点。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20, M = 1 << 20;

int f[M][N];
int n;
int w[N][N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> w[i][j];
    
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    for (int i = 0; i < 1 << n; i++)
        for (int j = 0; j < n; j++)
            if (i >> j & 1)
                for (int k = 0; k < n; k++)
                    if (i ^ (1 << j) >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}
/*

注意初始状态 ...0001 2^0 就是一开始就在0号点，距离不用走，所以是0

为什么从i从0 ~ 1 << n - 1 ？ 就是状态表示的所有点走一次

最终状态一定是 20个1 11111... 所以2^20次方-1就是20个1

然后枚举状态的每一位，看当前位是1的是从什么状态转移过来的

i ^ (1 << j) >> k => 表示求上一个状态
    当j=5时，表示在第五个点，求从哪个点转移到第5个点的
    ...100110(...里可能还有1， 所以k要枚举n次，因为不一定是从小于5的点转移过来的)
k=0 ...000110 &1 0
k=1 ...000011 &1 1
k=2 ...000001 &1 1
k=3 ...000000 &1 0
k=... 
*/

56、树形DP

例题：没有上司的舞会，Ural 大学有 \(N\) 名职员，编号为 \(1∼N\)。他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数，用整数 \(H_i\) 给出，其中 \(1≤i≤N\)。现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

第一行一个整数 \(N\)。

接下来 \(N\) 行，第 \(i\) 行表示 \(i\) 号职员的快乐指数 \(H_i\)。

接下来 \(N−1\) 行，每行输入一对整数 \(L,K\)，表示 \(K\) 是 \(L\) 的直接上司。（注意一下，后一个数是前一个数的父节点，不要搞反）。

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

image-20231213163327201

根据上图，我们发现：

  • 当不选节点 \(i\) ，影响最大高兴值的节点为 \(i\) 的子节点或其他节点
  • 当选 \(i\) 节点时，影响最大高兴值的节点只为 \(i\) 的子节点

由此我们可以得到状态转移方程：

  • 当 f[i][j] 时表示选 \(i\) 号节点

    很明显 \(i\) 号节点的快乐值要算上，子节点就不能算上了所以我们应该加 f[j][0]

  • 当 f[i][0] 时表示不选 \(i\) 号节点

    我们这时就不加 \(i\) 号的快乐值，如果不选 \(i\) ，那么 \(i\) 的子节点可选可不选，我们取最大 max(f[j][0],f[j][1])

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 6010;

int n;
int h[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
bool has_fa[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    f[u][1] = happy[u];

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);

        f[u][1] += f[j][0];
        f[u][0] += max(f[j][0], f[j][1]);
    }
}

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &happy[i]);

    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, a);
        has_fa[a] = true;
    }

    int root = 1;
    while (has_fa[root]) root ++ ;

    dfs(root);

    printf("%d\n", max(f[root][0], f[root][1]));

    return 0;
}

57、记忆化搜索

例题：滑雪，给定一个 \(R\) 行 \(C\) 列的矩阵，表示一个矩形网格滑雪场。矩阵中第 \(i\) 行第 \(j\) 列的点表示滑雪场的第 \(i\) 行第 \(j\) 列区域的高度。一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

输入一个矩阵

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

状态表示：f[i][j] 一条划到 (i,j) 的路径长度，属性： max

image-20231213164336739

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310;

int n, m;
int g[N][N], f[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dfs(int x, int y)
{
    if (f[x][y] != -1) return f[x][y];
    
    f[x][y] = 1;
    for (int i = 0; i < 4; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 1 && a <= n && b >= 1 && b <= m && g[a][b] > g[x][y])
            f[x][y] = max(f[x][y], dfs(a, b) + 1);
    }
    
    return f[x][y];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)    
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];
    memset(f, -1, sizeof f);
    
    int res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            res = max(res, dfs(i, j));
        
    cout << res << endl;
    return 0;
}

标签：...,int,基础,times,++,算法,include,模板,mod
From： https://www.cnblogs.com/yhgm/p/18094893

相关文章

  • Django框架之模板层
    【一】模板语法的传取值模板语法需要记两组符号，分别是{{}}和{%%}{{}}通常是与变量相关的{%%}通常是与逻辑相关的【1】传值模板语法可以传递python所有的数据类型，包括函数和类，以及类实例化的对象传递函数的时候，函数需要有返回值，要不然在页面显示的结果就是None模板语法......
  • 机器学习的核心算法 - CNN的原理探讨
    很悲哀，类似这样的技术性问题讨论，和其他很多我感兴趣的问题，我现在很多时候只能采用异步模式，比如发帖来解决，然后实时的交互，只能跟GPT聊。我找不到合适的朋友，对相关话题感兴趣，并且程度和我相当，能聊得下去。1引子- 梯度爆炸结论：梯度爆炸就是求参失败。sweetie，我是AI运算的小白......
  • JavaScript 基础 - 第1天
     了解变量、数据类型、运算符等基础概念，能够实现数据类型的转换，结合四则运算体会如何编程。体会现实世界中的事物与计算机的关系理解什么是数据并知道数据的分类理解变量存储数据的“容器”掌握常见运算符的使用，了解优先级关系知道JavaScript数据类型隐式转......
  • MySQL基础命令
    MySQL基础命令注：个人笔记，日常补修目录MySQL基础命令命令命令进入mysqlmysql-uroot-pEnterpassword:#展示数据库showdatabases;#创建数据库createdatabasexx;createdatabaseXX(数据库名)charset=(字符编码，例如utf8);createdatabaseifnotexistsXX(数......
  • 算法模板 v1.10.4.20240325
    算法模板v1.1.1.20240115：之前历史版本已不可寻，创建第一份算法模板。v1.2.1.20240116：删除“编译”-“手动开栈”；删除“编译”-“手动开O优化”；修改“编译”-“CF模板”；删除“读写”；删除“图论”-“欧拉图”-“混合图”；删除“图论”-“可达性统计”；删除“数据类型”-“高精类”。......
  • 数学基础板子（没有推导过程）
    \({\color{Red}声明：由于作者是个蒟蒻，所以本博客只含结论，不含推导过程。如果有大佬想看推导过程可以看(这里是传送门)}\)oi-wiki,教练，HaneDaniko素数筛法求素数用于求1~n的素数线性筛点击查看代码intprime[maxn];//保存素数boolis_not_prime[maxn]={1,1};//0和1......
  • 4.2.2、容器，算法，迭代器 初识
    了解STL中容器、算法、迭代器概念之后，我们利用代码感受STL的魅力STL中最常用的容器为Vector，可以理解为数组，下面我们将学习如何向这个容器中插入数据、并遍历这个容器1、vector存放内置数据类型容器：vector算法：for_each迭代器：vector<int>::iteratorvoidMyPrint(intval){ c......
  • day1:PHP语言基础、变量和常量
    一、PHP语言基础一种创建动态交互性站点的、强有力的服务器端脚本语言。1.PHP文件格式一个完整的PHP文件由HTML标记、PHP标记、PHP代码、注释和空格等元素构成。<Html><head><title>HelloWorld!</title></head><body><?php //输出Hello,World echo"Hello,World";......
  • 运动规划碰撞检测算法之GJK算法
    运动规划碰撞检测算法之GJK算法在自动驾驶系统运动规划模块的碰撞检测中，通常分为粗略碰撞检测和精细碰撞检测两个步骤。粗略碰撞检测用来将两个明显不相交的物体快速排除，使用外接圆的包围形或轴对齐包围矩形（AxisAlignedBoundingBox，AABB）都是比较好的方式。外接圆......
  • 06天【代码随想录算法训练营34期】 第三章 哈希表part01（● 242.有效的字母异位词 ●
    242.有效的字母异位词思路：26位的array，每个分别对应a,b,c...,z，如果遇到一个字母就++，如果两个array一样则为anagramhint:toinitiateanarraywithnelementscarryingvalue0:arr=[]arr=[0foriinrange(n)]print(arr)classSolution:defisAnagram(self,......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99