头像

ChenLing

广东某厂大




在线 


最近来访(31)
用户头像
辣鸡号航母
用户头像
yxc的小迷妹
用户头像
ACWing的用户
用户头像
迟早青
用户头像
xbrent
用户头像
Andy_37
用户头像
sweet_tea
用户头像
萝卜青菜
用户头像
Twinkle_wuwu
用户头像
Mellina
用户头像
Bochi酱
用户头像
LiuFan
用户头像
囵无
用户头像
啥也不会
用户头像
Evander.Liam
用户头像
NewBattery
用户头像
Bevis.
用户头像
acwing_83413


ChenLing
3小时前

背景

$\huge{一维差分扩展到二维,可以实现对某一个子矩阵的加减。}$

解析

二维差分数组.png

代码

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int b[N][N];

void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main()
{
    cin >> n >> m >> q;
    int x;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            scanf("%d", &x);
            insert(i, j, i, j, x);
        }

    int x1, y1, x2, y2, c;
    while (q --)
    {
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }

    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
            printf("%d ", b[i][j]);
        }
        puts("");
    }

    return 0;
}

核心代码

void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}



ChenLing
21小时前

背景

在 $O(1)$ 的时间复杂度实现对数组某一段 连续元素 加减同一个数的操作

求差分数组

求差分数组.png

怎么用

适用场景.png

代码

#include <iostream>

using namespace std;

const int N = 100010;

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

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
        b[i] = a[i] - a[i - 1];
    }

    int l, r, c;
    while (m --)
    {
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }

    for (int i = 1; i <= n; i ++)
    {
        a[i] = a[i - 1] + b[i];
        printf("%d ", a[i]);
    }

    return 0;
}

核心代码

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}



背景

一维数组的前缀和扩展到二维, 由求某一段长度的和变为求某个子矩阵的元素和.

求前缀和矩阵

求前缀和矩阵.png

求某个子矩阵的元素和

求子矩阵.png

代码

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int s[N][N];

int main()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            scanf("%d", &s[i][j]);
            s[i][j] = s[i - 1][j] + s[i][j - 1] + s[i][j] - s[i - 1][j - 1];
        }

    int x1, y1, x2, y2;
    while (q --)
    {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }

    return 0;
}



背景

当我们需要求得一个数的前 $n$ 个数的和的时候,其时间复杂度为 $O(n)$, 那么求得数组内某一段 $[l, r]$ 的和的时间复杂度就为 $O(n^2)$.
基于这种情况, 我们可以使用前缀和数组将时间复杂度优化为 $O(1)$.

常用于求某一段连续元素的和的情况.

原理解析

前缀和数组的公式为 $s[i]=s[i-1]+a[i]$, 翻译过来就是 $s[i]$ 表示 $a[[1]+a[2]+a[3]+…+a[i]$,
$$即:s[i]=a[1]+a[2]+a[3]+…+a[i]$$

求前缀和.png

怎么求某一段的元素和?

前缀和的使用.png

代码

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int s[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        scanf("%d", &s[i]);
        s[i] += s[i - 1];
    }

    int l, r;
    while (m --)
    {
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);
    }

    return 0;
}


活动打卡代码 AcWing 9. 分组背包问题

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

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

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++)
    {
        scanf("%d", &s[i]);
        for (int j = 0; j < s[i]; j ++)
            scanf("%d%d", &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 (j >= v[i][k])
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

    printf("%d\n", f[m]);

    return 0;
}



分析一波

分组背包.png

除了状态的存储多用了一维,最后还是01背包的解题思想 01背包详解

朴素代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

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

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++)
    {
        scanf("%d", &s[i]);
        for (int j = 0; j < s[i]; j ++)
            scanf("%d%d", &v[i][j], &w[i][j]);
    }

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

    printf("%d\n", f[n][m]);

    return 0;
}

一维状态优化

$\huge\textit{01背包优化看这里}$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int f[N];
int v[N][N], w[N][N], s[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 (j >= v[i][k])
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

    cout << f[m] << endl;

    return 0;
}

最后那里 01 背包的写法啊,由于需要先枚举组内的物品,再枚举体积,所以枚举体积的时候不能写成这样 for (int j = m; j >= v; j --),因为要获取到 v,我们需要得知具体是哪一个物品,所以需要 k,所以就写成 for (int j = m; j > 0; j --)



活动打卡代码 AcWing 4. 多重背包问题

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

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

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

    cout << f[n][m] << endl;

    return 0;
}


活动打卡代码 AcWing 5. 多重背包问题 II

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 11010, M = 2010;  //n * logm 个包

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

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

    int cnt = 0;    //这个是目标数组的下标
    for (int i = 1; i <= n; i ++)
    {
        int a, b, s;    //读取进来体积、价值、个数,然后打包存进数组
        scanf("%d%d%d", &a, &b, &s);
        int k = 1;  //打包的物品个数
        while (k <= s)
        {
            cnt ++;
            v[cnt] = a * k; //更新打包后的体积和价值
            w[cnt] = b * k;
            s -= k;         //总体积-打好包的体积
            k *= 2;         //打包数 * 2
        }
        if (s > 0)          //这里是多出来的那个孤儿
        {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt;                //更新最后的包的个数

    //接下来是01背包问题的求解过程了
    for (int i = 1; i <= n; i ++)
        // for (int j = 0; j <= m; j ++)
        // {
        //     f[i][j] = f[i - 1][j];
        //     if (j >= v[i])
        //       f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);

        // }
        for (int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

     printf("%d\n", f[m]);

    return 0;
}



分析一波

多重背包2.1.png

多重背包优化.png

代码如下

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010;  //n * logm 个包

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

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

    int cnt = 0;    //这个是目标数组的下标
    for (int i = 1; i <= n; i ++)
    {
        int a, b, s;    //读取进来体积、价值、个数,然后打包存进数组
        scanf("%d%d%d", &a, &b, &s);
        int k = 1;  //打包的物品个数
        while (k <= s)
        {
            cnt ++;
            v[cnt] = a * k; //更新打包后的体积和价值
            w[cnt] = b * k;
            s -= k;         //总体积-打好包的体积
            k *= 2;         //打包数 * 2
        }
        if (s > 0)          //这里是多出来的那个孤儿
        {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt;                //更新最后的包的个数

    //接下来是01背包问题的求解过程了
    for (int i = 1; i <= n; i ++)
        // for (int j = 0; j <= m; j ++)
        // {
        //     f[i][j] = f[i - 1][j];
        //     if (j >= v[i])
        //       f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);

        // }
        for (int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

     printf("%d\n", f[m]);

    return 0;
}

欸嘿!01背包不用一维优化的写法会 $\huge\color{red}{\textit{MLE}}$, 就是内存溢出,不行你试试。

总结

我觉得比较难想通的是求二进制阶乘的那一块,后面就是01背包的板子。




题目分析

$\huge{模板题目描述:}$

给定 n 个物品和一个体积为 m 的背包,每个物品都有自己的 体积v, 价值w, 个数s。求背包能装下的物品最大总价值。

yy分析法

朴素多重背包.png

代码如下

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

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

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

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

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

    cout << f[n][m] << endl;

    return 0;
}

代码2.0

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

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

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

    cout << f[n][m] << endl;

    return 0;
}

$\huge\color{green}{\textit{优化移步隔壁}}$$----->$$\huge\color{red}{\textit{多重背包II}}$

拓展联系一下

多重背包与完全背包一样都是以选的物品个数作为集合的划分标准。那么可不可以通过类似的方法将其优化成一维?
其实是不能,但是到目前为止,用多重背包的优化,这题也过,应该是 yxc 偷懒了。。。

  • 完全背包的取得的物品个数的限制是背包的体积,假设只能放下 s 个,所以计算 f[i, j-v] 的时候,只能有 $s-1$ 种可能,体积减去了一个嘛。
  • 但是多重背包就不一样了,它的限制是物品的数量,假设 j > (s + 1) * v 的时候,计算 f[i, j-v] 的时候,k 可以取到 s,那么这时候的 f[i, j-v] 就有了最后一项 f[i-i, j-(s+1)*v]+sw
  • 而多出来的这项也是无法通过整体减去一个 w 来抵消掉。那么就由于多了最后一项,那就不能将 f[i, j-v] 整体代入 f[i, j],所以无法用这种优化方法。

$\huge\color{blue}{完全背包的快速链接}$