蓝桥杯算法模板（D）
算法
蓝桥杯算法模板（D）
算法

蓝桥杯算法模板（D）

1、最长递增子序列

（1）题目描述：给定一个整数数组 nums，找到其中最长严格递增子序列的长度。

（2）算法思路：动态规划，dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。

（3）代码：

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int lengthOfLIS(int* nums, int numsSize) {
    // 动态开辟内存与初始化
    int *dp = (int *)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        dp[i] = 1;
    }

    // 动态规划
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = MAX(dp[i], dp[j] + 1);
            }
        }
    }

    // 找最大值
    int ans = 0;
    for (int i = 0; i < numsSize; i++) {
        ans = MAX(ans, dp[i]);
    }

    free(dp);
    return ans;
}

2、最长公共子序列

（1）题目描述：给定两个字符串 text1 和 text2，返回它们的最长公共子序列长度。

（2）算法思路：二维动态规划，dp[i][j] 表示 text1 前 i 个字符与 text2 前 j 个字符的最长公共子序列长度。

（3）代码：

#include <string.h>
#include <stdlib.h>

int longestCommonSubsequence(char* text1, char* text2) {
    int n = strlen(text1);
    int m = strlen(text2);

    // 申请 dp 数组
    int **dp = (int **)malloc((n + 1) * sizeof(int *));
    for (int i = 0; i <= n; i++) {
        dp[i] = (int *)malloc((m + 1) * sizeof(int));
    }

    // 初始化
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = 0;
        }
    }

    // 动态规划
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }

    int ans = dp[n][m];

    // 释放内存
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);

    return ans;
}

3、二维前缀和与差分数组

（1）题目描述：给定 n × m 的矩阵，进行 q 次区间修改，每次对子矩阵 [x1,y1] 到 [x2,y2] 加上 c，输出最终矩阵。

（2）算法思路：利用二维差分数组实现 O(1) 区间修改。

（3）代码：

#include <stdio.h>

#define MAXN 1005   // 可根据题目最大范围调整
#define MAXM 1005

long long a[MAXN][MAXM];
long long diff[MAXN][MAXM];

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

    // 读入原数组 a（从 1 开始）
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%lld", &a[i][j]);
        }
    }

    // 构建二维差分数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            diff[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];
        }
    }

    // 处理 q 次区间修改
    while (q--) {
        int x1, y1, x2, y2;
        long long c;
        scanf("%d %d %d %d %lld", &x1, &y1, &x2, &y2, &c);

        diff[x1][y1]       += c;
       diff[x2 + 1][y1]   -= c;
       diff[x1][y2 + 1]   -= c;
       diff[x2 + 1][y2 + 1] += c;
    }

    // 由差分数组还原最终数组 a
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            a[i][j] = diff[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    }

    // 输出结果
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            printf("%lld ", a[i][j]);
        }
        printf("\n");
    }

    return 0;
}

4、一维前缀和与差分数组

（1）题目描述：给定长度为 n 的数组，进行 q 次区间加操作，输出最终数组。

（2）算法思路：利用一维差分数组实现 O(1) 区间修改。

（3）代码：

#include <stdio.h>

#define MAXN 100005

long long a[MAXN];
long long diff[MAXN]; // 全局定义 等同于long long diff[MAXN] = {0};
long long temp[MAXN];

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

    // 读入原数组 a
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }

    // 处理 q 次区间加
    while (q--) {
        int l, r;
        long long c;
        scanf("%d %d %lld", &l, &r, &c);

        diff[l] += c;
        // 先确保不越界
        if (r + 1 <= n) {
            diff[r + 1] -= c;
        }
    }

    // 还原差分值
    for (int i = 1; i <= n; i++) {
        temp[i] = temp[i - 1] + diff[i];
    }

    // 输出结果（原数组 + 差分累加值）
    for (int i = 1; i <= n; i++) {
        printf("%lld ", a[i] + temp[i]);
    }
    printf("\n");

    return 0;
}

5、0-1背包

（1）题目描述：有 n 件物品，每件物品重量为 w，价值为 v，背包容量为 V，每件物品最多选一次，求最大价值。

（2）二维DP代码：

#include <stdio.h>

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

    // dp[i][j]：只考虑前 i 个物品，背包容量为 j 时的最大价值
    int dp[n + 1][V + 1];

    // 初始化
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= V; j++) {
            dp[i][j] = 0;
        }
    }

    for (int i = 1; i <= n; i++) {
        int w, v;
        scanf("%d %d", &w, &v);

        for (int j = 1; j <= V; j++) {
            if (j >= w) {
                // 选 or 不选
                int not_take = dp[i - 1][j];
                int take = dp[i - 1][j - w] + v;
                dp[i][j] = not_take > take ? not_take : take;
            } else {
                // 装不下，只能不选
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    printf("%d\n", dp[n][V]);
    return 0;
}

（3）一维DP代码：

#include <stdio.h>
#include <stdlib.h>

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

    // dp[j]：背包容量为 j 时的最大价值
    int *dp = (int *)malloc((V + 1) * sizeof(int));

    // 初始化为 0
    for (int j = 0; j <= V; j++) {
        dp[j] = 0;
    }

    for (int i = 1; i <= n; i++) {
        int w, v;
        scanf("%d %d", &w, &v);

        // ⚠️ 关键：容量必须从大到小遍历
        for (int j = V; j >= w; j--) {
            int not_take = dp[j];
            int take = dp[j - w] + v;
            dp[j] = not_take > take ? not_take : take;
        }
    }

    printf("%d\n", dp[V]);

    free(dp);
    return 0;
}

6、完全背包

（1）题目描述：有 n 件物品，每件物品可以选无限次，求背包容量为 V 时的最大价值。

（2）核心区别：与 0-1 背包相比，选了一次物品后还能继续选该物品。

（3）差异代码：

一、
// 0-1 背包
dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)

// 完全背包
dp[i][j] = max(dp[i-1][j], dp[i][j-wi] + vi)
//                  ↑ 注意这里是 dp[i] 不是 dp[i-1]


二、
N, V = map(int, input().split())
dp = [0] * (V + 1)

for _ in range(N):
    w, v = map(int, input().split())

    # 关键：容量 j 正序遍历
    for j in range(w, V + 1):
        dp[j] = max(dp[j], dp[j - w] + v)

print(dp[V])

7、多重背包

（1）题目描述：有 n 种物品，第 i 种物品最多有 s[i] 件，每件重量为 w，价值为 v，求最大价值。

（2）代码：

#include <stdio.h>
#include <stdlib.h>

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

    // 二进制拆分后，物品数量最多是 N * log(s)
    int *W = (int *)malloc(sizeof(int) * 200000);
    int *Val = (int *)malloc(sizeof(int) * 200000);
    int cnt = 0;  // 记录拆分后物品的真实数量

    // 读取每种物品并进行二进制拆分
    for (int i = 0; i < N; i++) {
        int w, v, s;
        scanf("%d %d %d", &w, &v, &s);

        int k = 1;
        while (s >= k) {
            W[cnt] = k * w;
            Val[cnt] = k * v;
            cnt++;
            s -= k;
            k *= 2
        }

        // 处理剩余部分
        if (s > 0) {
            W[cnt] = s * w;
            Val[cnt] = s * v;
            cnt++;
        }
    }

    // 0-1 背包 DP 数组
    int *dp = (int *)malloc(sizeof(int) * (V + 1));
    for (int j = 0; j <= V; j++) {
        dp[j] = 0;
    }

    // 标准 0-1 背包
    for (int i = 0; i < cnt; i++) {
        for (int j = V; j >= W[i]; j--) {
            if (dp[j] < dp[j - W[i]] + Val[i]) {
                dp[j] = dp[j - W[i]] + Val[i];
            }
        }
    }

    printf("%d\n", dp[V]);

    // 释放内存
    free(W);
    free(Val);
    free(dp);

    return 0;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注