1.分治

1.1 递归分治

p6001-归并排序

题目：

Description

​ 给定一个长度为n的数列，包含n个整数。你的任务是编写一个程序，使用归并排序算法将这个数列按照升序排列，并输出排序后的数列。

Input

​ 第一行包含一个整数n，表示数列中的元素个数。

​ 第二行包含n个整数，数列中的每个元素，整数之间由空格分隔。

Output

​ 输出一行，包含n个整数，为按照升序排列后的数列，整数之间由空格分隔。在行末输出一个换行符。

解题思路：

​ 掌握归并排序的分治思想，采用递归分解成一个一个小问题，最后小问题汇总成大问题。归并排序算法有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。

img

代码：

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
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
// 由于需要先递归到最深处，且在第三次走到结点位置时才需要进行计算，所以应该是头递归（即递归应该放在正常函数的前面）
void merge(vector<int>& nums, int l, int r){
    vector<int> temp;
    int mid = (r+l)/2+1;
    int i = l, j = mid;
    while(i < mid && j <= r){
        if(nums[i] <= nums[j]){
            temp.push_back(nums[i]);
            i++;
        }
        else{
            temp.push_back(nums[j]);
            j++;
        }
    }
    while(i < mid){
        temp.push_back(nums[i]);
        i++;
    }
    while(j <= r){
        temp.push_back(nums[j]);
        j++;
    }
    for(int i = l; i <= r; i++){
        nums[i] = temp[i-l];
    }
}

void mergeSort(vector<int>& nums, int l, int r){
    if(l >= r){
        return;
    }
    int mid = (r+l)/2;
    mergeSort(nums, l, mid);
    mergeSort(nums, mid+1, r);
    merge(nums, l, r);
}


int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    mergeSort(nums, 0, n-1);
    for(int i = 0; i < n; i++){
       cout <<  nums[i] << ' ';
    }
    return 0;
}

p6002-求逆序对的数量

题目：

Description

​ 给定一个长度为n的整数数列，你的目标是计算出数列中逆序对的总数。逆序对定义为数列中一对元素(a[i], a[j])，其中i < j且a[i] > a[j]。

Input

​ 第一行包含一个整数n，表示数列中的元素个数。

​ 第二行包含n个整数，表示数列的元素，元素之间由一个空格分隔。

Output

​ 输出一个整数，表示数列中逆序对的总数。

解题思路：

​ 由于在归并排序两个数组merge的过程中，我们需要新开一个temp数组来将两边的数组进行排序，这时一旦左半边的nums[i]大于右半边的nums[j]，那么从第i个开始到左半边的结束全是逆序对。相当于求逆序对的数量，比归并排序就多了一行代码。

代码：

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
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
long long num = 0;

void merge(vector<long long>& nums, int l, int r){
    vector<long long> temp;
    int mid = (r+l)/2+1;
    int i = l, j = mid;
    while(i < mid && j <= r){
        if(nums[i] <= nums[j]){
            temp.push_back(nums[i]);
            i++;
        }
        else{
            temp.push_back(nums[j]);
            // 在归并排序的过程中就可以查找，与归并排序唯一不同的地方就是在此处计算了逆序对的数量
            // 如果nums[i] > nums[j]，那么从i到mid全是逆序对。
            num += (mid-i);
            j++;
        }
    }
    while(i < mid){
        temp.push_back(nums[i]);
        i++;
    }
    while(j <= r){
        temp.push_back(nums[j]);
        j++;
    }
    for(int i = l; i <= r; i++){
        nums[i] = temp[i-l];
    }
}

void mergeSort(vector<long long>& nums, int l, int r){
    if(l >= r){
        return;
    }
    int mid = (r+l)/2;
    mergeSort(nums, l, mid);
    mergeSort(nums, mid+1, r);
    merge(nums, l, r);
}


int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<long long> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    mergeSort(nums, 0, n-1);
    cout << num;
    return 0;
}

p6003-求第k小的数

题目：

Description

​ 给定一个长度为n的整数数列和一个整数k，你需要编写一个程序，使用快速选择算法找出并返回数列中第k小的元素。

Input

​ 第一行包含两个整数n和k。

​ 第二行包含n个整数，这些整数构成你需要处理的数列，每两个整数之间用空格分隔。

Output

​ 输出仅包含一个整数，即数列中第k小的元素。

解题思路：

​ 快速排序采用“分治”的思想，对于一组数据，选择一个基准元素（base），通常选择第一个或最后一个元素，通过第一轮扫描，比base小的元素都在base左边，比base大的元素都在base右边，再有同样的方法递归排序这两部分，直到序列中所有数据均有序为止。

​ 本题采用在快速排序的过程中找到第k小的数。分治思想。因为快排每一次是找到这一块数的第一个数在整个数组的正确位置，所以我们在每次快排完后确认该数是不是第k个数就可以了，如果不是就根据k的大小遍历左边还是右边。

代码：

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
#include <bits/stdc++.h>
using namespace std;
int n, k;

int quickSort(vector<int>& nums, int l, int r){
    int i = l, j = r;
    int x = nums[l];
    while(i < j){
        while(i < j && nums[j] >= x){
            j--;
        }
        if(i < j){
            nums[i++] = nums[j];
        }
        while(i < j && nums[i] < x){
            i++;
        }
        if(i < j){
            nums[j--] = nums[i];
        }
    }
    nums[i] = x;
    if(k == i+1){
        return nums[i];
    }
    else if(k > i+1){
        return quickSort(nums, i+1, r);
    }
    else{
        return quickSort(nums, l, i);
    }
}

int main(int argc, char const *argv[])
{
    cin >> n >> k;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    
    cout << quickSort(nums,0,n-1);
    return 0;
}

p6004-快速幂

题目：

Description

​ 给定n组整数ai, bi, pi，你需要编写一个程序来计算每组(ai^bi) mod pi的结果。

Input

​ 第一行包含一个整数n，表示数据组数。

​ 接下来的n行，每行包含三个整数ai, bi, pi。

Output

​ 对于每组输入数据，输出一个整数，即计算得到的(ai^bi) mod pi的值。每个结果输出在单独的一行。

解题思路：

​ 快速幂（Fast Powering）是一种用于高效计算指数幂的算法。它的基本思想是通过将指数进行二进制拆分，并利用指数的二进制表示来减少乘法运算次数。

​ 具体而言，假设我们要计算一个数的n次幂，我们可以将n表示为二进制形式，例如，n的二进制表示为1101，那么我们可以将n的次幂表示为：

​ a^n = a^(2^0 * 1) * a^(2^1 * 0) * a^(2^2 * 1) * a^(2^3 * 1)

​ 可以观察到，n的二进制表示中的每一位对应着该位置上的幂次项是否需要相乘。如果该位是1，我们就需要将对应的幂次项乘到结果中，如果该位是0，我们则不需要。

​ 利用这个观察，我们可以通过迭代的方式计算幂次项的乘积。假设我们已经计算出了a^(2^i)，那么我们可以通过将其平方得到a^(2^(i+1))。这样，我们可以利用迭代来计算出所有的幂次项，从而得到最终的结果。

代码：

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
#include <bits/stdc++.h>
using namespace std;

long long quickPow(long long a, long long b, long long p){
    a = a % p;
    long long result = 1;
    while(b > 0){
        if(b % 2 == 1){
            result = (result * a) % p;
        }
        a = (a * a) % p;
        b /= 2;
    }
    return result;
}

int main(int argc, char const *argv[])
{
    int n;
    long long a, b, p;
    cin >> n;
    while(n--){
        cin >> a >> b >> p;
        cout << quickPow(a, b, p) << endl;  
    }
    
    return 0;
}

p6005-最大连续子数组和

题目：

Description

​ 给定一个整数数组nums，找出其中的连续子数组（至少包含一个元素）使得该子数组的和最大，并返回这个最大的和。

Input

​ 第一行一个整数n，代表数组的大小

​ 第二行，一个整数数组nums，其中1 <= nums.length <= 1000且-10^4 <= nums[i] <= 10^4。

Output

​ 返回该数组中具有最大和的连续子数组的和。

解题思路：

​ 分治思想，想到上方的经典分治图，先递归到最深处再慢慢合起来，所以此处应该是头递归。合的过程中，我们要找到最大的连续子数组，由于我们已经找到左边的最大和右边的最大，还差的就是包含了中间元素的最大。因为最开始两边是截断的，现在合起来了就必须考虑中间的最大。所以最终有三种情况，比较求其最大值，找max(左边的最大，右边的最大，包含中间元素的最大)。

代码：

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
#include <bits/stdc++.h>
using namespace std;

int maxSum(vector<int>& nums, int l, int r){
    if(l >= r){
        return nums[l];
    }
    int mid = (l+r)/2;
    int lmax = maxSum(nums, l, mid);
    int rmax = maxSum(nums, mid+1, r);
    int midSum = 0;
    int msum, msum1 = -INT_MAX, msum2 = -INT_MAX;
    for(int i = mid; i >= l; i--){
        midSum += nums[i];
        msum1 = max(midSum, msum1);
    }
    midSum = 0;
    for(int i = mid; i <= r; i++){
        midSum += nums[i];
        msum2 = max(midSum, msum2);
    }
    msum = msum1+msum2-nums[mid];
    return max(msum, max(lmax, rmax));
}

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    cout << maxSum(nums, 0, n-1);
    return 0;
}

1.2 二分法

二分有两种经典的写法：

第一种写法：

​ 我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。

​ 区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：

  • while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
  • if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

第二种写法：

​ 如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同。

有如下两点：

  • while (left < right)，这里使用 < ,因为**left == right在区间[left, right)**是没有意义的
  • if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

p6011-有序数组中查找数1

题目：

Description

​ 给定一个严格单调递增的序列，这个序列经过一次旋转后，可能在某个枢轴点上发生了旋转，导致原有序列被分为两部分，前面部分的所有元素都大于后面部分的所有元素，如下图所示：

1
2
原始序列：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
旋转后的序列：4 -> 5 -> 6 -> 7 -> 1 -> 2 -> 3

​ 旋转后的序列依旧保持了分段的单调递增特性。请编写一个算法，找出并返回旋转后序列中的最小元素。

​ 假设序列中不存在重复元素。

Input

  • 第一行 n, (0 < n < 10000000)
  • 第二行，n个整数，一个整数数组，代表旋转后的序列。

Output

​ 序列中的最小元素。

解题思路：

​ 使用二分查找。由于给定的序列是严格单调递增的，并且经过一次旋转后可能发生了旋转，我们可以利用这个性质来缩小查找范围。首先初始化左边界l为序列的起始位置，右边界r为序列的结束位置。进行二分查找。在每次迭代中，计算出中点mid，即(l + r) / 2。我们可以比较mid位置的元素与左边界l位置的元素以及右边界r位置的元素。

  • 如果mid位置的元素大于等于左边界l位置的元素，说明mid位置在旋转点之前，即左半部分是有序的。此时，我们可以将左边界l更新为mid+1，继续在右半部分进行查找。

  • 如果mid位置的元素小于等于右边界r位置的元素，说明mid位置在旋转点之后，即右半部分是有序的。此时，我们可以将右边界r更新为mid-1，继续在左半部分进行查找。

    重复上方，直到找到旋转点。当左边界l和右边界r相遇时，即找到了旋转点。

代码：

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 <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n;
  // 关闭输入输出缓存，使效率提升
	ios::sync_with_stdio(false);
	// 解除cin和cout的默认绑定，来降低IO的负担使效率提升
	cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    int l = 0, r = n-1, mid;
  if(nums[l] < nums[r]){
  	cout << nums[l];
    return 0;
  }
    while(l < r){
        mid = (l+r)/2;
        if(nums[mid] >= nums[0]){
            l = mid+1;
        }
        else{
            r = mid;
        }
    }
    cout << nums[l];
    return 0;
}

p6012-有序数列中查找数2

题目：

Description

实现一个算法，在一个升序排列的整数数组中找到一个给定整数k的起始位置和终止位置。如果这个整数在数组中出现多次，起始位置指的是k首次出现的索引(索引从0开始计算)，终止位置是k最后一次出现的索引。如果k在数组中没有出现，则需要返回一对-1。

Input

  • 第一行包含两个整数n和q，其中n是数组的长度，q是查询的次数。
  • 第二行包含n个升序排列的整数，表示数组的内容。
  • 接下来的q行，每行包含一个整数k，表示需要查询的数字。

Output

  • 对于每个查询，输出一行，包含两个整数，即数字k的起始位置和终止位置。
  • 如果数组中不存在该元素，则输出-1 -1。

解题思路：

​ 利用二分查找，先找左边界，再找右边界。找左边界时将r尽量往左边缩短，等于的时候依然往左。找右边界时将l尽量往右边缩短，等于的时候依然往右。二分主要就是边界问题，左边界往左压，右边界往右压。

代码：

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
#include <bits/stdc++.h>
using namespace std;

int leftDivideTwo(vector<int> nums, int k){
    int l = 0, r = nums.size()-1;
    while(l <= r){
        int mid = (r-l)/2 + l;
        if(nums[mid] >= k){
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    return nums[l] == k? l: -1;
}

int rightDivideTwo(vector<int> nums, int k){
    int l = 0, r = nums.size()-1;
    while(l <= r){
        int mid = (r-l)/2 + l;
        if(nums[mid] > k){
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    return nums[r] == k? r: -1;
}


int main(int argc, char const *argv[])
{
    int n, q;
    cin >> n >> q;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    while(q--){
        int k;
        cin >> k;
        cout << leftDivideTwo(nums, k) << ' ' << rightDivideTwo(nums, k) << endl;
    }
    return 0;
}

p6013-求数的三次方根

题目：

Description

在一片森林里，有 n 棵树，每棵树的高度不相同。伐木工人需要从这些树中砍下 k 段等长的木材。为了使得所砍的木材尽可能地长，需要确定砍树时每段木材的最大可能长度。要求输出的木材长度是整数。

Input

  • 第一行输入包含两个整数 n 和 k，其中 n 表示树的总数，k 表示需要砍下的木材段数。
  • 第二行输入包含 n 个整数，每个整数表示一棵树的高度。

Output

  • 输出一个整数，表示伐木工人能砍得的最长木材长度。

解题思路：

​ 在这个算法中，我们首先初始化左边界l为数据的左范围-10000，右边界r为数据的右范围10000。然后，我们不断将区间长度除以2，直到达到指定的精度。

​ 在每一次迭代中，我们计算出中点mid，即(l + r) / 2，并根据问题的要求进行相应的操作。根据问题的性质，我们可以根据mid的取值调整左边界l或右边界r的值，以逐渐缩小区间。这样，我们可以通过二分查找的方式逼近所求的答案。注意 r - l的取值与所求答案要求精度, 一般比要求高的 2。

代码：

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 <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    double n;
    cin >> n;
    double l = -1e4, r = 1e4;
    while(r-l > 1e-8){
        double mid = (r+l)/2;
        if(mid * mid * mid < n){
            l = mid;
        }
        else if(mid * mid * mid > n){
            r = mid;
        }
        else{
            printf("%.6f", mid);
            return 0;
        }
    }
    printf("%.6f", l);
    return 0;
}

p6014-砍树

题目：

Description

在一片森林里，有 n 棵树，每棵树的高度不相同。伐木工人需要从这些树中砍下 k 段等长的木材。为了使得所砍的木材尽可能地长，需要确定砍树时每段木材的最大可能长度。要求输出的木材长度是整数。

Input

  • 第一行输入包含两个整数 n 和 k，其中 n 表示树的总数，k 表示需要砍下的木材段数。
  • 第二行输入包含 n 个整数，每个整数表示一棵树的高度。

Output

  • 输出一个整数，表示伐木工人能砍得的最长木材长度。

解题思路：

​ 我们的目标是找到最高的树。我们将使用二分查找的方法来确定每个符合要求的段的长度，并将其赋值给一个变量。这个变量将始终保持递增。

​ 首先，我们需要确定二分查找的左边界l和右边界r。左边界l可以设为0，表示树的最低高度，而右边界r可以根据问题的要求来确定，通常是已知的树的最高高度。

​ 然后，我们开始进行二分查找。在每次迭代中，我们计算出中点mid，即(l + r) / 2，并根据问题的要求来判断mid是否符合要求。如果mid符合要求，我们将其赋值给一个变量，并更新左边界l为mid，以继续向右侧搜索更高的树。如果mid不符合要求，我们更新右边界r为mid，以缩小搜索范围，继续向左侧搜索更低的树。

​ 通过这种二分查找的方法，我们可以逐步逼近最高的树的高度，并将符合要求的高度赋值给一个变量。由于我们每次只考虑符合要求的段，因此这个变量只会越来越大。最后，当二分查找结束时，我们就可以得到最高的树的高度。

代码：

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
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
  
// 关闭输入输出缓存，使效率提升
	ios::sync_with_stdio(false);
	// 解除cin和cout的默认绑定，来降低IO的负担使效率提升
	cin.tie(NULL); cout.tie(NULL);    
  long long n, k;
    cin >> n >> k;
    long long m = 0;
    vector<long long> nums(n);
    long long ans = 0;
    for(int i = 0; i < n; i++){
        cin >> nums[i];
        m = max(m, nums[i]);
    }
    long long l = 0, r = m;
    while(l < r){
        long long sum = 0;
        long long mid = (l+r+1)/2;
        for(long long x: nums){
            sum += (x/mid);
        }
        if(sum >= k){
            ans = mid;
            l = mid;
        }
        else if(sum < k){
            r = mid-1;
        }
    }

    cout << ans;
    return 0;
}

p6015-数列分段

题目：

Description

对于一个长度为 N 的正整数数列，现要将其分成 M 段（M ≤ N），要求每段连续，并使每段的和的最大值尽可能小。

Input

  • 第一行包含两个正整数 N 和 M。
  • 第二行包含 N 个由空格隔开的非负整数，表示数列中的每个元素。

Output

  • 输出一个正整数，表示分段后每段和的最大值的最小可能值。

解题思路：

​ 我们的目标是找到一种分割方式，使得分割后的每段和的最大值尽可能小。首先，我们需要找到分成一段的情况下的最大和，即将所有数相加得到的总和r。这个最大和r可以作为二分查找的右边界。

​ 然后，我们从0到r开始进行二分查找。在每次迭代中，我们计算出中点mid，即(l + r) / 2，并遍历整个数组，检查是否存在一种分割方式，使得每段的和不超过mid。

​ 如果存在这样的分割方式，我们将更新右边界r为mid-1，以继续向左侧搜索更小的和。这是因为我们希望找到最小的满足条件的和。

​ 如果不存在这样的分割方式，我们将更新左边界l为mid+1，以继续向右侧搜索更大的和。

​ 通过不断地二分查找，我们最终将找到满足条件的最小和。这个和即为每段和的最大值。

代码：

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
#include <bits/stdc++.h>
using namespace std;

// cnt计算段数，当最后算出来的段数小于等于要求的段数的时候，才能符合要求
// 例子：假设我和小于等于10，分了6段，但是我只需要5段，这个时候10变小，就只能分出和更大的段，不符合要求，所以要返回cnt<=k。
bool check(vector<int> nums,  int l, int r, int k, int mid){
    int sum = 0;
    int cnt = 1;
    int i = 0;
    while(i < nums.size()){
        if(sum + nums[i] <= mid){
            sum += nums[i];
        }
        else{
            cnt++;
            sum = nums[i];
        }
        i++;
    }
    return cnt <= k;
}

int main(int argc, char const *argv[])
{
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    int h = 0;
    for(int i = 0; i < n; i++){
        cin >> nums[i];
        h += nums[i];
    }
    int l = 0, r = h;
    int ans = INT_MAX;
    while(l <= r){
        int mid = (l+r)/2;
        if(check(nums, l, r, k, mid)){
            ans = min(ans, mid);
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }
    cout << ans;
    return 0;
}

2.贪心

2.1 简单贪心

p7001-采购礼物

题目：

Description

​ 小明的生日即将到来，他的朋友小红决定为他挑选一些礼物。在礼物商店中，有n种不同的礼物，每种礼物都有一个确定的价格。但小红只带了m单位的钱，她想知道，最多可以为小明买到多少件礼物？

​ 请你设计一个算法，帮助小红计算出她最多可以为小明买到多少件礼物。每种物品只买一件。

Input

​ 第一行包含两个整数n和m，分别表示礼物的种类数量和小红携带的钱数。（1 <= n <= 10^5, 1 <= m <= 10^9）

​ 第二行包含n个整数，表示每种礼物的价格。每件礼物的价格为正整数并且不超过10^4。

Output

​ 输出一个整数，表示小红最多可以为小明买到的礼物数量。

解题思路：

​ 每次优先选价格小的礼物就可以买到更多的礼物。

代码：

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
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n, money;
    cin >> n >> money;
    vector<int> price(n);
    for(int i = 0; i < n; i++){
        cin >> price[i];
    }
    sort(price.begin(), price.end());
    int num = 0;
    for(int i = 0; i < n; i++){
        money -= price[i];
        if(money < 0){
            break;
        }
        else{
            num += 1;
        }
    }
    cout << num;
    return 0;
}

p7002-硬币找零

题目：

Description

​ Alice在学校的小店里工作，她的任务是售卖各种小零食和饮料。每当有顾客购买商品并付款后，她需要给顾客找零。在小店中，找零硬币的面值有1、5、10、20和50。Alice想要通过使用最少的硬币数量来找零，这样既可以减少小店的零钱消耗，又可以方便顾客。

​ 现在，假设一个顾客购买的商品总价是(100 - n)元，顾客递给Alice一张100元的纸币。请设计一个算法，计算Alice最少需要使用多少张硬币来找给顾客(100 - n)元的零钱。

Input

​ 输入一整数n (1 <= n <= 99)，表示顾客购买商品的总价。

Output

​ 输出一个整数，表示最少需要使用的硬币数量。

解题思路：

​ 每次都尽量找面值大的钱，就可以找最少使用的钱。

代码：

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
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int change = 100 - n;
    int num = 0;
    while(change != 0){
        if(change >= 50){
            num += 1;
            change -= 50;
        }
        else if(change >= 20 && change < 50){
            num += 1;
            change -= 20;
        }
        else if(change >= 10 && change < 20){
            num += 1;
            change -= 10;
        }
        else if(change >= 5 && change < 10){
            num += 1;
            change -= 5;
        }
        else if(change >= 1 && change < 5){
            num += 1;
            change -= 1;
        }
    }
    cout << num;
    return 0;
}

p7003-部分背包问题

题目：

Description

​ 在一个古老的金矿中，矿工们找到了n（0 < n <= 100）堆不同重量和价值的金币。由于他们只有一个小袋子，所以不能把所有的金币都搬走。小袋子最多能装T（0 < T <= 1000）单位的重量。每堆金币有一个总重量m和总价值v，且 1 <= m, v <= 100。

​ 矿工们想知道，他们应该如何选择和分割金币堆，以便他们可以携带走最大价值的金币。

​ 请你设计一个算法，计算矿工们可以携带走的金币的最大价值。

Input

​ 第一行包含两个整数n和T，分别表示金币堆的数量和小袋子的最大承重。

​ 接下来的n行，每行包含两个浮点数，分别是第i堆金币总重量m和总价值v。

Output

​ 输出一个小数，表示矿工们可以携带走的金币的最大价值，结果保留两位小数。

解题思路：

这个问题与背包问题不同的地方在于我们可以逐个选择金币而不是必须一次性取走所有金币。因此，我们可以通过一种贪心的策略来解决这个问题。

具体步骤如下：

  1. 首先，我们计算每堆金币的平均价值。将每堆金币的总价值除以堆中金币的数量，得到平均价值。
  2. 接下来，我们按照平均价值的降序对所有金币堆进行排序。这样，我们就可以先选择平均价值最大的金币堆进行拿取。
  3. 依次遍历排序后的金币堆列表，按照降序选择金币堆并逐个拿取。我们先选择平均价值最大的金币堆，然后选择平均价值次大的金币堆，以此类推。

代码：

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
#include <bits/stdc++.h>
using namespace std;

bool compare(const vector<double> &a, const vector<double> &b) {
    return a[2] > b[2];
}

int main(int argc, char const *argv[])
{
    int n, t;
    cin >> n >> t;
    vector<vector<double>> nums(n, vector<double>(3, 0));
    for(int i = 0; i < n; i++){
        cin >> nums[i][0] >> nums[i][1];
        nums[i][2] = nums[i][1]/nums[i][0];
    }
    double sum = 0;
    sort(nums.begin(), nums.end(), compare);
    // 这里的sum处理的比较巧妙。
    for(int i = 0; i < n; i++){
        if(t >= nums[i][0]){
            sum += nums[i][1];
            t -= nums[i][0];
        }
        else{
            sum += nums[i][2] * t;
            break;
        }
    }
    printf("%.2f", sum);

    return 0;
}

2.2 区间贪心

p7004-区间选点

题目：

Description

​ 给定 ( N ) 个闭区间 ([a_i, b_i])，需要在数轴上选择尽可能少的点，以确保每个区间内至少包含一个选出的点。位于区间端点上的点也算作区间内。

Input

  • 第一行包含整数 ( N )，表示区间数量。
  • 接下来的 ( N ) 行，每行包含两个整数 ( a_i, b_i )，表示一个区间的两个端点。

数据范围

  • ( 1 <= N <= 10^5 )
  • ( -10^9 <= a_i <= b_i <= 10^9 )

Output

  • 输出一个整数，表示所需选择的点的最小数量。

解题思路：

​ 当面临一个区间贪心问题时，一种常见的思路是对区间按照左边界或者右边界进行排序。如果我们按照右边界进行排序，那么我们可以从最左边的区间开始遍历；如果按照左边界进行排序，我们则可以从最右边的区间开始遍历。

​ 这种排序的思路可以帮助我们更好地处理区间之间的关系。通过排序，我们可以确保在遍历过程中，当前区间的右边界（或左边界）是已经遍历的区间中最小（或最大）的。这样做的好处是，在选择下一个区间时，我们可以根据当前区间的右边界（或左边界）来判断是否与下一个区间有重叠或符合某些特定的条件。

代码：

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
#include <bits/stdc++.h>
using namespace std;

struct node
{
    int l, r;
};

bool compare(const node &a, const node &b){
    return a.r < b.r;
}

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<node> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i].l >> nums[i].r;
    }
    sort(nums.begin(), nums.end(), compare);
    int cnt = 1;
    for(int i = 0; i < n; ){
        int x = nums[i].r;
        while(i < n && x >= nums[i].l){
            i++;
        }
        if(i == n){
            break;
        }
        cnt++;
    }
    cout << cnt;
    return 0;
}

p7005-最优活动安排

题目：

Description

​ 假设你是一个活动策划者，你有n个活动需要在同一天举办。每个活动有一个开始时间和结束时间，我们可以假设它们都是整数，并且在同一时间内只能进行一个活动。你的任务是安排这些活动，以便可以举办尽可能多的活动。

Input

​ 输入的第一行包含一个整数n（1 <= n <= 10^6），表示活动的数量。

​ 接下来的n行，每行包含两个整数s和f（0 <= s < f <= 10^9），表示活动的开始时间和结束时间。

Output

​ 返回可以举办的最大活动数量。

解题思路：

​ 当我们面临需要安排更多活动的问题时，可以采用按照活动的结束时间进行排序的策略，并从最左边的活动开始遍历。这种排序方式的目的是为了优先选择那些结束时间较早的活动，以便为后续活动留下更多的时间。

​ 通过按照结束时间排序，我们可以保证在遍历过程中，当前活动的结束时间是已经遍历的活动中最早的。这样，在选择下一个活动时，我们可以根据当前活动的结束时间来判断是否与下一个活动有重叠或满足其他特定的条件。

​ 该题与p7004思想基本相同。

代码：

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
#include <bits/stdc++.h>
using namespace std;

struct node
{
    int l, r;
};

bool compare(const node &a, const node &b){
    return a.r < b.r;
}

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<node> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i].l >> nums[i].r;
    }
    sort(nums.begin(), nums.end(), compare);
    int cnt = 1;
    for(int i = 0; i < n; ){
        int x = nums[i].r;
        while(i < n && x > nums[i].l){
            i++;
        }
        if(i == n){
            break;
        }
        cnt++;
    }
    cout << cnt;
    return 0;
}

p7006-区间覆盖

题目：

Description

​ 给定 N 个闭区间 [a_i, b_i] 以及一个指定的线段区间 [s, t] ，需要选择尽可能少的区间来完全覆盖指定的线段区间。

Input

  • 第一行包含两个整数 ( s ) 和 ( t )，表示给定线段区间的两个端点。
  • 第二行包含整数 ( N )，表示给定的区间数量。
  • 接下来的 ( N ) 行，每行包含两个整数 ( a_i, b_i )，表示一个区间的两个端点。

数据范围：

  • ( 1 <= N <= 10^5 )
  • ( -10^9 <= a_i <= b_i <= 10^9 )
  • ( -10^9 <= s <= t <= 10^9 )

Output

  • 输出一个整数，表示所需的最少区间数。
  • 如果无法完全覆盖给定的线段区间，则输出 (-1)。

解题思路：

​ 我们首先按照区间的左边界从小到大进行排序。这样，我们可以确保在遍历过程中，当前考虑的区间的左边界是已经遍历的区间中最小的。

​ 接下来，我们使用一个循环来遍历排序后的区间。在每次循环中，我们会尝试找到一个覆盖尽可能少的区间。具体而言，我们在目标左边界的范围内查找数组区间中最大的右边界。

​ 我们可以使用一个计数器来记录已选择的区间数量。开始时，计数器为0。然后，我们使用一个for循环来遍历排序后的区间。在每次循环中，我们检查当前区间的左边界是否在目标左边界的范围内。如果是，我们更新目标左边界为当前区间的右边界，并将计数器加一，表示我们已经选择了这个区间。

​ 接下来，我们继续循环，寻找下一个覆盖尽可能少的区间。我们重复这个过程，直到遍历完所有的区间。

代码：

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
#include <bits/stdc++.h>
using namespace std;

struct node
{
    int l, r;
};

bool compare(const node &a, const node &b){
    return a.l < b.l;
}

int main(int argc, char const *argv[])
{
    int s, t;
    cin >> s >> t;
    int n;
    cin >> n;
    vector<node> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i].l >> nums[i].r;
    }
    sort(nums.begin(), nums.end(), compare);
    int cnt = 0, j, rmax;
    bool is_success;
    for(int i = 0; i < n; i++){
        j = i, rmax=-INT_MAX;
        while(j < n && nums[j].l <= s){
            rmax = max(rmax, nums[j].r);
            j++;
        }
        if(rmax < s){
            is_success = false;
            break;
        }
        else{
            s = rmax;
            cnt++;
            if(s >= t){
                is_success = true;
                break;
            }
        }
    }
    if (is_success == false) cout << -1 << endl;
    else cout << cnt << endl;
    return 0;
}

p7007-数列分段

题目：

Description

​ 给定一个长度为 ( N ) 的正整数数列 ( A_i )，需要将其分割成若干连续的子段，使得每个子段的元素和不超过 ( M )（可以等于 ( M )）。目标是找出最少能将数列分成多少段，以满足上述条件。

Input

  • 第一行包含两个正整数 ( N, M )，分别表示数列 ( A_i ) 的长度和每段的最大和。
  • 第二行包含 ( N ) 个由空格隔开的非负整数 ( A_i )。

数据范围：

  • ( 1 <= N <= 10^5 )
  • ( 1 <= M <= 10^9 )
  • ( 1 <= A_i <= M )

Output

  • 输出一个正整数，表示最少划分的段数。

解题思路：

​ 按for循环顺序依次更新每段长度使得每段长度最逼近m即可，计数器加一，然后重新开始记录每段长度。

代码：

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
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n, m;
    cin >> n >> m;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    int sum = 0;
    int cnt = 1;
    for(int i = 0; i < n; i++){
        if(sum + nums[i] <= m){
            sum += nums[i];
        }
        else{
            cnt++;
            sum = nums[i];
        }
    }
    cout << cnt;
    return 0;
}

2.3 实际场景贪心

p7011-股票交易

题目：

Description

​ 你是一位股票交易员，你现在有一支股票的价格列表，其中第i天的股票价格是prices[i]。设计一个算法来找到获取最大利润的交易策略。交易规则如下：

  • 你可以进行多次交易，但是必须在再次购买前卖出股票。

    请返回你能获得的最大利润。

Input

  • 第一行一个整数n
  • n个正整数（小于1000），代表一个数组prices，其中prices[i]代表股票在第i天的价格。

Output

​ 返回你能获取的最大利润。

解题思路：

​ 只要后项大于前项，则累加到结果中。想象连续两次涨，就累加了两次的差值，其实就等于 第三次卖 - 第一次买的差值。所以把所有的差值加起来就是最大的利润。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    int sum = 0;
    for(int i = 0; i < n-1; i++){
        if(nums[i] < nums[i+1]){
            sum += (nums[i+1]-nums[i]);
        }
    }
    cout << sum;
    return 0;
}

p7012-排队接水

题目：

Description

​ 有n个人需要排队到一个水龙头处打水。每个人打水所需的时间不同。第i个人打水需要t_i时间单位。我们的目标是安排一个打水的顺序，使得所有人的总等待时间最小。

​ 这里的“等待时间”指的是一个人在排队等待打水时所花费的时间。例如，如果一个人排在第一个，那么他的等待时间是 0，因为他不需要等待其他人。但是，排在他后面的人需要等待他打完水。

Input

  • 第一行是一个整数n(a <= n <= 1e5) ，表示排队的人数。
  • 第二行包含n个整数，每个整数t_i(1 <= t_i <= 1e4) 表示第i个人打水所需的时间。

Output

  • 输出一个整数，这个整数是所有人等待时间的总和的最小值。

解题思路：

​ 由于每个人都要打水，肯定是时间花费越少的人在前面打，这样后面人的总等待时间就会越少，所以按从小到大排序，再计算时间即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    sort(nums.begin(), nums.end());
    int sum = 0;
    for(int i = 0; i < n; i++){
        sum += (n-1-i) * nums[i];
    }
    cout << sum;
    return 0;
}

p7013-仓库选址

题目：

Description

​ 在一条数轴上有N家商店，每家商店都有一个确定的坐标，这些坐标分别为A_1, A_2, ..., A_N。你的任务是在这条数轴上选择一个点建立一个货仓。

​ 每天早晨，需要从货仓运送货物到每家商店。为了提高运输效率，你需要选择一个货仓的位置，使得货仓到所有商店的总距离最小。

Input

  • 第一行是一个整数N(1 < N < 1e5) ，表示商店的数量。
  • 第二行是N个整数，A_1, A_2, ..., A_N(0 < A_i < 1e4) ，表示每家商店在数轴上的坐标。

Output

  • 输出一个整数，表示货仓到所有商店的总距离的最小可能值。

解题思路：

​ 总距离最小就必须得建到中间，先把数组从小到大排序，很容易理解将仓库建到所有数据的正中间距离是最小的，因为无论是建到两个数据的左边或者右边，他到两个数据的距离都会比建到两个数据的中间长。而建到中间的话距离就等于两个数据的差值，直接计算差值即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    sort(nums.begin(), nums.end());
    int l = 0, r = n-1;
    int sum = 0;
    while(l < r){
        sum += (nums[r]-nums[l]);
        l++;
        r--;
    }
    cout << sum;
    return 0;
}

p7014-均分图书

题目：

Description

​ 在学校图书馆，管理员小明正在整理一些图书。这些图书被分成了n堆，编号分别为1, 2, ..., n。每堆上有若干本书，但图书的总数必为n的倍数。小明可以在任一堆上取若干本图书，然后移动它们。

​ 移动图书的规则为：

  • 在编号为1的堆上取的图书，只能移到编号为2的堆上；

  • 在编号为n的堆上取的图书，只能移到编号为n-1的堆上；

  • 在其他编号的堆上取的图书，可以移到相邻左边或右边的堆上。

    ​ 现在要求你帮助小明找出一种移动方法，用最少的移动次数使每堆上图书的数量都一样多。

Input

  • 第一行输入一个整数n(1 <= n <= 100)，表示图书堆的数量。
  • 第二行输入n个整数a_1, a_2, ... , a_n(1 <= a_i <= 1e5)，用空格隔开，表示每堆图书初始时的数量。保证图书总数是n的倍数。

Output

  • 输出一个整数，表示使所有堆均达到相等时的最少移动次数。

解题思路：

​ 因为不等于均值的图书的数据，最少都需要移动一次，所以我遍历整个数组，每个元素我都将他变成均值，要不就是多了给右边，要不就是少于均值从右边拿（那可能会右边不够你拿怎么办？其实没有影响，因为你这一次虽然是拿右边是不够的，但是其实顺序无所谓，本质上你可能是右边的右边先给了右边，然后你再从右边拿的，这个顺序是不影响最后拿的次数的。），等于均值了就不管，然后使用一个计数器计数就可以解决问题。

代码：

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
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> nums(n);
    int sum = 0;
    for(int i = 0; i < n; i++){
        cin >> nums[i];
        sum += nums[i];
    }
    int average = sum / n;
    int cnt = 0;
    for(int i = 0; i < n-1; i++){
        if(nums[i] > average){
            nums[i+1] += (nums[i]-average);
            cnt++;
        }
        else if(nums[i] < average){
            nums[i+1] -= (average-nums[i]);
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}

p7015-合并果子

题目：

Description

  1. 有 n 种果子，每种果子的数量分别为 a1, a2, …, an。
  2. 你可以合并任意两堆果子，每次合并的体力消耗是这两堆果子的总数。
  3. 需要通过 n-1 次合并，使得最终合并的总体力消耗最小。

计算出达达合并所有果子所需的最小体力消耗值。

Input

  • 输入包括两行，第一行是一个整数 n ( 1 <= n <= 1e4)，表示果子的种类数。
  • 第二行包含 n 个整数，分别是每种果子的数量。( 1 <= a_i <= 1e4)

Output

  • 输出是一个整数，表示最小的体力消耗值。

解题思路：

​ 要想体力消耗小，那么数量小的肯定要先合并。首先数组从小到大排，将最小的2个合并成一个a。因为合并之后这个a不一定是最小的了，所以a和后面的元素要重新排序，再找出最小的两个再合并，直到最后合并成一堆。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    int cost = 0;
    for(int i = 0; i < n-1; i++){
        sort(nums.begin()+i, nums.end());
        cost += (nums[i]+nums[i+1]);
        nums[i+1] += nums[i];
    }
    cout << cost;
    return 0;
}

3.动态规划

一些小tips：

​ 解这种dp问题时他的题目问求什么什么的最大或者最长，一般dp[i]就是求前i个或者以第i个为结尾的最大或最长的。

3.1 线性DP

p5002-爬楼梯

题目：

Description

​ 假设你正在爬楼梯，楼梯共有n个阶梯。每次你可以爬1或2个阶梯。计算有多少种不同的方法可以爬到楼梯的顶部。

Input

  • 一个正整数n``（ 1 <= n <= 50 ），表示楼梯的阶梯数。

Output

  • 输出一个整数，表示总的方法数。

解题思路：

​ 到达第n阶楼梯有两种方式，从第n-2阶上2步，从第n-1阶上一步，所以得到的状态转移方程为：

1
2
3
4
5
dp[0] = 1;  // 0级楼梯，只有1种方式（不走）
dp[1] = 1;  // 1级楼梯，只有1种方式
for(int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
}

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    if(n == 1){
        cout << 1;
        exit(0);
    }
    if(n == 2){
        cout << 2;
        exit(0);
    }
    vector<long long> dp(n+1,0);
    dp[1]=1;
    dp[2]=2;
    for(int i = 3; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    cout << dp[n];
}

p5003-连续子数组最大和

题目：

Description

​ 给定一个整数数组nums，找出其中的连续子数组（至少包含一个元素）使得该子数组的和最大，并返回这个最大的和。

Input

  • 第一行一个整数n，代表数组的大小
  • 第二行，一个整数数组nums，其中1 <= nums.length <= 10^4且-10^4 <= nums[i] <= 10^4。

Output

  • 返回该数组中具有最大和的连续子数组的和。

解题思路：

​ dp[i]是以第i个元素为结尾的最大连续子数组和，而这个和有两种情况，一种是，要么就是以i-1为结束的和加上第i个数，要么就是只有第i个数，所以得到的状态转移方程为：

1
2
3
4
for(int i = 1; i < n; i++){
      // 递推公式：dp[i]要么就是上一个加上这个元素，要么就是本身这个元素。
        dp[i] = max(dp[i-1]+res[i], res[i]);
    }

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

// 最大连续子数组和
int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> res(n);
    for(int i = 0; i < n; i++){
        cin >> res[i];
    }
    vector<int> dp(n, 0);
    for(int i = 1; i < n; i++){
      // 递推公式：dp[i]要么就是上一个加上这个元素，要么就是本身这个元素。
        dp[i] = max(dp[i-1]+res[i], res[i]);
    }
    cout << *max_element(dp.begin(), dp.end());
    return 0;
}

p5004-最长上升子序列

题目：

Description

​ 给定一个长度为n``(1 <= n <= 5000) )的正整数序列，其中每个整数不超过10^6，确定最长严格递增子序列的长度。

​ 递增子序列是原序列的一个子集，其中选取的整数是按原顺序并且严格递增的。

Input

  • 第一行包含一个单独的整数n，表示序列的长度。
  • 第二行由n个由空格分隔的整数组成，代表该序列。

Output

​ 输出一个单独的整数，代表最长递增子序列的长度。

解题思路：

​ dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度。dp[i]只有两种情况，要么就是上一步的最大，要么就是新遍历的这个dp最大。该题会将i之前的元素都遍历一遍，找到最大的递增子序列。状态转移方程为：

1
2
3
4
5
6
7
8
9
for(int i = 1; i < n; i++){
        // 将i之前的元素都遍历一遍，找到最大的递增子序列
        for(int j = 0; j < i; j++){
            if(res[i] > res[j]){
                // 递推公式，要么就是之前的最大，要么就就是信遍历的这个比较大。
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
    }

代码：

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 <bits/stdc++.h>
using namespace std;
// 最长递增子序列
int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> res(n);
    for(int i = 0; i < n; i++){
        cin >> res[i];
    }
    vector<int> dp(n, 1);
    for(int i = 1; i < n; i++){
        // 将i之前的元素都遍历一遍，找到最大的递增子序列
        for(int j = 0; j < i; j++){
            if(res[i] > res[j]){
                // 递推公式，要么就是之前的最大，要么就就是信遍历的这个比较大。
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
    }
    cout << *max_element(dp.begin(), dp.end());
    return 0;
}

p5005-打家劫舍

力扣上面有相关变形题：

198. 打家劫舍 - 力扣（LeetCode）

题目：

Description

​ 你是一名独行小偷，计划在夜间沿一条街偷取房屋中的财宝。每间房屋内都有一定数量的金币。但有一个问题，这些房屋都装有连通的报警系统。如果你选择偷取两栋相邻的房屋，警报将会响起。

Input

  • 第一行输入一个整数n,（1 <= n <= 100）表示房屋的数量。
  • 第二行输入n个整数，用空格分隔，表示每个房屋中的金币数量（0 <= 金币数量 <= 400）。

Output

​ 输出一个整数，表示你今晚能偷取的最大金额。

解题思路：

​ dp[i]表示前i个房子能偷的最多钱。而在处理第i个房子的时候，无非两种情况，偷与不偷。如果不偷第i个房子的话，那么前i个房子偷的最多钱肯定和前i-1个房子偷的最多钱是一样的，即dp[i]=dp[i-1]。如果偷第i个房子的话，那么第i-1个房子一定不偷，那么这就与前i-2个房子赚的最多钱相关，即dp[i-2]+nums[i]。状态转移方程为：

1
2
3
4
// dp[i]表示前i个房子能偷的最多钱
    for(int i = 2; i < n; i++){
        dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
    }

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    vector<int> dp(n);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    // dp[i]表示前i个房子能偷的最多钱
    for(int i = 2; i < n; i++){
        dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
    }
    cout << *max_element(dp.begin(), dp.end());
    return 0;
}

3.2 二维DP

p5001-数字三角形最大路径和

题目：

Description

​ 给定一个数字三角形，你的任务是找到从三角形的顶部到底部的路径，使得路径上经过的数字之和最大。在每一步，你只能移动到下一行中相邻的数字上。

例如，给定以下数字三角形：

1
2
3
4
5
    7
   3 8
  8 1 0
 2 7 4 4
4 5 2 6 5

从7 -> 3 -> 8 -> 7 -> 5的路径产生最大的和30。

Input

  • 第一行：一个正整数 r （ 1 <= r <= 1000），表示数字三角形的行数。
  • 接下来的 r 行：第 i 行包含 i 个整数，表示数字三角形的第 i 行。

所有输入数字在 [0, 100] 范围内。

Output

  • 输出一个整数，表示从三角形顶部到底部的最大路径和。

解题思路：

​ dp[i][j]代表第i行第j列的最大和，这个和会选取上一行和自己相邻的两个和的最大值，在加上nums[i][j]，状态转移方程为：

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i = 1; i < n; i++){
       for(int j = 0; j <= i; j++){
           if(j == 0){
               dp[i][j] = dp[i-1][j]+nums[i][j];
           }
           else if(j == i){
               dp[i][j] = dp[i-1][j-1] + nums[i][j];
           }
           else{
               dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + nums[i][j];
           }
       }
   }

代码：

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
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<vector<int>> nums(n, vector<int>(n, 0));
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= i; j++){
            cin >> nums[i][j];
        }
    }
    vector<vector<int>> dp(n, vector<int>(n, 0));
    dp[0][0] = nums[0][0];
    for(int i = 1; i < n; i++){
        for(int j = 0; j <= i; j++){
            if(j == 0){
                dp[i][j] = dp[i-1][j]+nums[i][j];
            }
            else if(j == i){
                dp[i][j] = dp[i-1][j-1] + nums[i][j];
            }
            else{
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + nums[i][j];
            }
        }
    }
    cout << *max_element(dp[n-1].begin(), dp[n-1].end());
    return 0;
}

p5006-最长公共子序列

题目：

Description

​ 给定两个字符串A和B，你需要找出它们之间的最长公共子序列的长度。

Input

  • 第一行：两个整数N和M，分别表示字符串A和B的长度。(1≤N,M≤1000)
  • 第二行：长度为N的字符串A。
  • 第三行：长度为M的字符串B。

Output

  • 输出一个整数，代表最长公共子序列的长度。

解题思路：

​ 经典的字符串二维dp，dp[i][j]代表s1前i个字符和s2前j个字符的最长公共子序列长度。两个for循环即可解决。当s1[i] == s2[j]时，dp直接由i-1和j-1即可得到，如果不相等的话就由dp[i-1][j], dp[i][j-1]两种状态的最大值转移而来，为什么不考虑dp[i-1][j-1]呢，因为这个是一定小于等于上方两个的。状态转移方程为：

1
2
3
4
5
6
7
8
9
10
11
12
for(int i = 1; i <= n; i++){
       for(int j = 1; j <= m; j++){
           // 相等的话直接由i-1和j-1即可得到
           if(s1[i] == s2[j]){
               dp[i][j] = dp[i-1][j-1]+1;
           }
           // 不相等的话就由以下两种状态转移而来，为什么不考虑dp[i-1][j-1]呢，因为这个是一定小于等于这两个的。
           else{
               dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
           }
       }
   }

代码：

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 <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n, m;
    cin >> n >> m;
    string s1, s2;
    cin >> s1 >> s2;
    // dp[i][j]代表s1的前i个字符和s2的前j个字符的最长公共子序列长度。
    vector<vector<int>> dp(s1.size()+1, vector<int>(s2.size()+1));
    for(int i = 0; i <= n; i++){
        dp[i][0] = 0;
    }
    for(int j = 0; j <= m; j++){
        dp[0][j] = 0;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            // 相等的话直接由i-1和j-1即可得到
            if(s1[i] == s2[j]){
                dp[i][j] = dp[i-1][j-1]+1;
            }
            // 不相等的话就由以下两种状态转移而来，为什么不考虑dp[i-1][j-1]呢，因为这个是一定小于等于这两个的。
            else{
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    cout << dp[n][m];
    return 0;
}

p5007-字符串编辑距离

题目：

Description

​ 给定两个字符串 A 和 B，你的任务是计算将 A 转换为 B 所需的最少操作数。你可以进行以下三种操作：

  1. 删除 A 中的一个字符。
  2. 向 A 中插入一个字符。
  3. 替换 A 中的一个字符为另一个字符。

请你计算将 A 转换为 B 所需的最小操作数。

Input

  • 第一行：一个整数 n，表示字符串 A 的长度。
  • 第二行：一个长度为 n 的字符串 A。
  • 第三行：一个整数 m，表示字符串 B 的长度。
  • 第四行：一个长度为 m 的字符串 B。

字符串中仅包含大小写字母。

Output

​ 输出一个整数，表示从A转换到B所需的最小操作数。

解题思路：

​ 这是一道经典的字符串变换二维DP，解题思路与状态转移方程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for(int i = 1; i <= n; i++){
       for(int j = 1; j <= m; j++){
           // 如果最后一个字符相等，就直接等于上一个
           // 这里为什么是i-1和j-1，因为字符串里面0代表是第一个，1代表是第二个，和dp数组里面不一样
           // dp里面前i个就是dp[i]，而s1里面第i个就算s1[i-1]
           if(s1[i-1] == s2[j-1]){
               dp[i][j] = dp[i-1][j-1];
           }
           // 如果最后一个不相等，分三种情况，替换：dp[i-1][j-1]，然后把s1[i]换成s2[j]
           // 删除：dp[i-1][j]，先将s1[i]删了，然后就变成了s1的前i-1个变成s2的前j个的次数。
           // 添加：dp[i][j-1]，先把s1的前i个字符变成s2的前j-1个字符，再在s1后面加一个s2[j]。
           else{
               dp[i][j] = min(dp[i-1][j-1], dp[i-1][j])+1;
               dp[i][j] = min(dp[i][j], dp[i][j-1]+1);
           }
       }
   }

代码：

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
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n, m;
    string s1, s2;
    cin >> n >> s1 >> m >> s2;
    //dp[i][j]代表s1的前i个字符转换成s2的前j个字符需要的最少次数
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    for(int i = 0; i <= n; i++){
        dp[i][0] = i;
    }
    for(int j = 0; j <= m; j++){
        dp[0][j] = j;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            // 如果最后一个字符相等，就直接等于上一个
            // 这里为什么是i-1和j-1，因为字符串里面0代表是第一个，1代表是第二个，和dp数组里面不一样
            // dp里面前i个就是dp[i]，而s1里面第i个就算s1[i-1]
            if(s1[i-1] == s2[j-1]){
                dp[i][j] = dp[i-1][j-1];
            }
            // 如果最后一个不相等，分三种情况，替换：dp[i-1][j-1]，然后把s1[i]换成s2[j]
            // 删除：dp[i-1][j]，先将s1[i]删了，然后就变成了s1的前i-1个变成s2的前j个的次数。
            // 添加：dp[i][j-1]，先把s1的前i个字符变成s2的前j-1个字符，再在s1后面加一个s2[j]。
            else{
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j])+1;
                dp[i][j] = min(dp[i][j], dp[i][j-1]+1);
            }
        }
    }
    cout << dp[n][m];
    return 0;
}

3.3 背包问题

p5011-0-1背包

题目：

Description

​ 给定 N 件物品和一个容量为 V 的背包。每件物品只能使用一次。

​ 第i件物品的体积是vi，价值是wi。

​ 你的任务是决定将哪些物品装入背包，以使得这些物品的总体积不超过背包容量，同时总价值最大。请输出最大价值。

Input

  • 第一行包含两个整数，分别为N和V，表示物品数量和背包容量。
  • 接下来的 N 行，每行包含两个整数vi和wi，表示第i件物品的体积和价值。

Output

​ 输出一个整数，表示最大价值。

解题思路：

​ 二维dp，dp[i][j]代表在前i个物品里面任意选，装进容量为j的背包里面获得的最大价值。解题思路和代码转移方程为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for(int i = 1; i <= n; i++){
        for(int j = 1; j <= v; j++){
            // 两种情况，装weight[i]和不装。
            // 不装的话就和装前i-1个一样。
            // 装的话最大就是前i-1个装入容量为j-weight[i]的背包中的价值再加上weight[i]的价值。
            // 为什么是减weight[i]，如果减的比weight[i]小（假设减了a），你说有可能是j-a个容量没装满，也能装下weight[i]。
            // 但是我们已经知道了j-weight[i]的最大价值，如果要j-a比j-weight[i]价值大，那么必须装j-weight[i]装不下而j-a装得下的，那如果再装，剩下的容量肯定就不够装weight[i]。
            // 所以在要装下weight[i]的前提下，j-a的价值是一定等于j-weight[i]的。
            // 为什么是减weight[i]，如果减的比weight[i]大（假设减了a）。那这肯定是小于等于j-weight[i]的最大价值的。
            if(j >= weight[i-1]){
                // 为什么是weight[i-1]和value[i-1]，因为你在weight和value数组中第i个数是weight[i-1]
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]]+value[i-1]);
            }
            // 装不下weight[i]
            else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }

代码：

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
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n, v;
    cin >> n >> v;
    vector<int> weight(n);
    vector<int> value(n);
    for(int i = 0; i < n; i++){
        cin >> weight[i] >> value[i];
    }
    // dp[i][j]表示选前i个物品装入容量为j的背包里的最大价值
    vector<vector<int>> dp(n+1, vector<int>(v+1, 0));
    for(int i = 0; i <= n; i++){
        dp[i][0] = 0;
    }
    for(int j = 0; j <= v; j++){
        dp[0][j] = 0;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= v; j++){
            // 两种情况，装weight[i]和不装。
            // 不装的话就和装前i-1个一样。
            // 装的话最大就是前i-1个装入容量为j-weight[i]的背包中的价值再加上weight[i]的价值。
            // 为什么是减weight[i]，如果减的比weight[i]小（假设减了a），你说有可能是j-a个容量没装满，也能装下weight[i]。
            // 但是我们已经知道了j-weight[i]的最大价值，如果要j-a比j-weight[i]价值大，那么必须装j-weight[i]装不下而j-a装得下的，那如果再装，剩下的容量肯定就不够装weight[i]。
            // 所以在要装下weight[i]的前提下，j-a的价值是一定等于j-weight[i]的。
            // 为什么是减weight[i]，如果减的比weight[i]大（假设减了a）。那这肯定是小于等于j-weight[i]的最大价值的。
            if(j >= weight[i-1]){
                // 为什么是weight[i-1]和value[i-1]，因为你在weight和value数组中第i个数是weight[i-1]
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]]+value[i-1]);
            }
            // 装不下weight[i]
            else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[n][v];
    return 0;
}

p5012-多重背包

题目：

Description

​ 你有一个背包，容量为V，以及N种不同类型的物品。每种物品有限数量供选择。

对于第i种物品：

  • 它有s_i件可用。
  • 每件的体积是v_i。
  • 每件的价值是w_i。

​ 请确定如何选择物品放入背包，以确保所选物品的总体积不超过背包的容量，并使所选物品的总价值最大化。输出能够获得的最大价值。

Input

  • 第一行：两个整数，分别代表物品的种数N和背包的容积V。
  • 接下来的N行：每行包含三个整数，代表一种物品的体积v_i、价值w_i和数量s_i。

Output

  • 输出一个整数，表示能够获得的最大价值。

解题思路：

​ 每种物品有限个，把他挨个放入weight和value中就变形为01背包了。或者利用完全背包的思想，三重for循环。

代码：

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
// 多重背包 
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int NR = 110;
int v[NR], w[NR], s[NR];
int dp[NR][NR];

int main() {
    int n, m;
    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++) {
            if(j < v[i]) dp[i][j] = dp[i - 1][j];
            else{
                for(int k = 0; k <= s[i] && v[i] * k <= j; k++)
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i] * k] + w[i] * k);
            }
        }
    printf("%d", dp[n][m]);
    return 0;
}

p5013-完全背包

题目：

Description

​ 有一个背包，它的容量为V。还有N种不同类型的物品，每种物品都有无限数量可供选择。

​ 每种物品的体积为v_i，价值为w_i。

​ 请你确定如何选择物品放入背包，以确保物品的总体积不超过背包的容量，并且物品的总价值达到最大。你需要输出最大的价值。

Input

  • 第一行：两个整数，分别代表物品的种数N和背包的容积V。
  • 接下来的N行：每行包含两个整数，分别代表一种物品的体积v_i和价值w_i。

Output

​ 输出一个整数，表示能够获得的最大价值。

解题思路：

与01背包唯一不同的地方就是：

1
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]]+value[i-1]);

改成了

1
dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i-1]]+value[i-1]);

是因为他的代码思想发生了一些变化，看以下代码就能明白，本来是三重循环：

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
// 完全背包 朴素 
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int NR = 1010;
int v[NR], w[NR];
int dp[NR][NR];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) {
            if(j < v[i]) dp[i][j] = dp[i - 1][j];
            else{
                for(int k = 0; k * v[i] <= j; k++)
                {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - k* v[i]] + k * w[i]);
                }
            }
        }
    printf("%d", dp[n][m]);
    return 0;
}

//k的for循环优化
// dp[i][j] = max(dp[i][j], 
//        dp[i-1][j-v] + w,  dp[i-1][j-2v] + 2w, dp[i-1][j-3v] + 3w,..) 
// dp[i][j-v] = 
//        dp[i-1][j-v],  dp[i-1][j-2v] + w, dp[i-1][j-3v] + 2w,..)

在进行k的for循环优化之后的代码：

代码：

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
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n, v;
    cin >> n >> v;
    vector<int> weight(n);
    vector<int> value(n);
    for(int i = 0; i < n; i++){
        cin >> weight[i] >> value[i];
    }
    // dp[i][j]表示选前i个物品装入容量为j的背包里的最大价值
    vector<vector<int>> dp(n+1, vector<int>(v+1, 0));
    for(int i = 0; i <= n; i++){
        dp[i][0] = 0;
    }
    for(int j = 0; j <= v; j++){
        dp[0][j] = 0;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= v; j++){
            if(j < weight[i-1]){
                dp[i][j] = dp[i-1][j];
            }
            else{
                dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i-1]]+value[i-1]);
            }
        }
    }
    cout << dp[n][v];
    return 0;
}

3.4 区间DP

p5014-股票交易

力扣的相关题目：

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

123. 买卖股票的最佳时机 III - 力扣（LeetCode）

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

题目：

Description

​ 你是一位股票交易员，你现在有一支股票的价格列表，其中第i天的股票价格是prices[i]。设计一个算法来找到获取最大利润的交易策略。交易规则如下：

  • 你可以进行多次交易，但是必须在再次购买前卖出股票。

  • 卖出股票后，你不能在当日立即买入（次日可以买卖），也就是必须等待至少一天（冷冻期为一天）。

    请返回你能获得的最大利润。

Input

  • 第一行一个整数n
  • n个正整数（小于1000），代表一个数组prices，其中prices[i]代表股票在第i天的价格。

Output

​ 返回你能获取的最大利润。

解题思路：

​ 关键的dp数组含义：dp[i][j]中，j只有0和1两个取值。dp[i][0]代表第i天不持有股票，dp[i][1]代表第i天持有股票，最后答案求dp[n-1][0]即可（因为dp[i][0]随着i的变大是越来越大的，后面的肯定是最大的。）

1
2
3
4
// 如果第i天不持有股票的话，那么有两种情况：若前一天也不持有股票，那么第i天肯定和前一天相等，因为第i天没有买也没卖。若前一天持有股票，那么第i天肯定卖掉了，要加上今天的价格。
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+nums[i]);
// 如果第i天持有股票的话也有两种情况：若前一天也持有股票，那么第i天肯定和前一天相等，因为第i天没有买也没卖。若前一天没持有股票，那么第i天肯定买入了，减去今天买入的价格。
dp[i][1] = max(dp[i-1][0]-nums[i], dp[i-1][1]);

代码：

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
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    // dp[i][1]代表第i天持有股票的股票的利润
    // dp[i][0]代表第i天不持有股票的股票的利润
    vector<vector<int>> dp(n, vector<int>(2, 0));
    dp[0][0] = 0;
    dp[0][1] = -nums[0];
    for(int i = 1; i < n; i++){
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]+nums[i]);
        dp[i][1] = max(dp[i-1][0]-nums[i], dp[i-1][1]);
    }
    // for(int i = 0; i < n; i++){
    //     for(int j = 0; j < 2; j++){
    //         cout << dp[i][j] << ' ';
    //     }
    //     cout << endl;
    // }
    cout << dp[n-1][0];
    return 0;
}

p5015-石子合并

题目：

Description

你有N堆石子排成一行。每堆石子有一定的重量，用整数数组表示。你需要通过一系列操作将所有石子合并成一堆。在每次操作中，你可以选择相邻的两堆石子进行合并。合并的代价为这两堆石子的重量之和，合并后新的一堆石子的重量也为这两堆石子的重量之和。

由于合并的顺序不同，最终的合并代价也会不同。你的任务是找到一种合并顺序，使得合并所有石子的总代价最小，并输出这个最小的合并代价。

Input

  • 第一行包含一个整数N，表示石子的堆数。
  • 第二行包含N个整数，每个整数表示一堆石子的重量。

Output

  • 输出一个整数，表示最小的合并代价。

解题思路：

​ 经典区间dp，dp[i][j]代表合并第i个石子到第j个石子需要的最小代价，二维dp取上三角，从左下往右上循环。eg：初始化的是对角线的四个元素，然后求上面斜着的三个元素，再求上方斜着的两个元素，最后求右上角的元素。

image-20240109110226714

状态转移方程为：

1
2
3
4
5
6
7
8
9
10
11
for(int len = 2; len <= n; len++){
        // 从第一个石子开始遍历
        for(int l = 1; l + len-1 <= n; l++){
            int r = l+len-1;
            // 在找最小代价的时候要把范围内的合并方法都遍历一遍找最小值。
            for(int k = l; k < r; k++){
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + s[r]-s[l-1]);
            }

        }
    }

代码：

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
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> nums(n+1);
    vector<int> s(n+1);
    for(int i = 1; i <= n; i++){
        cin >> nums[i];
        s[i] = s[i-1] + nums[i];
    }
    //dp[i][j]代表合并第i个到第j个石子需要的最小代价
    vector<vector<int>> dp(n+1, vector<int>(n+1, INT_MAX));
    // 这个dp的下三角是不放东西的，而我们要求的是dp[0][n]，在右上角
    // 所以得从下面往上面走dp，很容易想到先初始化对角线为0，
    // 从左下往右上走意味着我们要一步一步把斜着的填满。
    for(int i = 1; i <= n; i++){
        dp[i][i] = 0;
    }
    // 遍历合并的石子的数量
    for(int len = 2; len <= n; len++){
        // 从第一个石子开始遍历
        for(int l = 1; l + len-1 <= n; l++){
            int r = l+len-1;
            // 在找最小代价的时候要把范围内的合并方法都遍历一遍找最小值。
            for(int k = l; k < r; k++){
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + s[r]-s[l-1]);
            }

        }
    }
    cout << dp[1][n];
    return 0;
}

4.回溯

回溯算法理论基础：

代码随想录 (programmercarl.com)

看到回溯脑子里时刻想着这一个树形模板，帮助理解。

回溯算法理论基础

回溯代码模板

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

4.1 子集排列问题

p8001-枚举子集2

题目：

Description

​ 写一个递归函数，枚举n个数{x_1 , ... , x_n}中取若干个数的每种方法（子集枚举）. 对每种方法把取出的数从小到大排序，若两种方法中前k-1个数的选取情况相同，则取了第k个数的在前. 例如对n=4,X={100,20,3,4},应该按如下顺序给出结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
100,20,3,4
100,20,3
100,20,4
100,20
100,3,4
100,3
100,4
100
20,3,4
20,3
20,4
20
3,4
3
4

Input

​ 第一行一个正整数n。

​ 第二行n个正整数。

Output

​ 输出2^n行，每行一个子集，按题目要求排序。

解题思路：

​ 还是套用经典的回溯模板，首先查看输出顺序，因为要先输出原本的数组，所以应该先递归到最深处，然后再输出，故cout应该在dfs后面，利用一个startindex保证数组每次都是从起始的后面开始遍历的，预防重复情况出现。

代码：

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
#include <bits/stdc++.h>
using namespace std;

vector<int> res;

void dfs(vector<int> nums, int startIndex){
    for(int i = startIndex; i < nums.size(); i++){
        res.push_back(nums[i]);
        dfs(nums, i+1);
        for(int j = 0; j < res.size(); j++){
            cout << res[j] << ' ';
        }
        cout << endl;
        res.pop_back();
    }
}

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    dfs(nums, 0);
    return 0;
}

额外-枚举子集3

题目：

​ 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

​ 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

解题思路：

​ 思路与枚举子集2差不多，但是他有重复数字，为了排除重复数字的干扰，需要先对输入数组排序，将重复数字变相邻，方便设置一个used数组，判断是否重复使用该数字。

代码随想录 (programmercarl.com)

代码：

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
#include <bits/stdc++.h>
using namespace std;

vector<int> used(100000, 0); 
vector<int> res;
void dfs(vector<int> nums, int startindex){
    if(startindex == nums.size()){
        return;
    }
    for(int i = startindex;i < nums.size(); i++){
        if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false){
            continue;
        }
        else{
            res.push_back(nums[i]);
            used[i] = true;
            dfs(nums, i+1);
                    for(int i = 0; i < res.size(); i++){
            cout << res[i] << ' ';
        }
        cout << endl;
            used[i] = false;
            res.pop_back();
        }
    }
}

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    sort(nums.begin(), nums.end();
    dfs(nums, 0);
    return 0;
}

p8002-全排列

题目：

Description

​ 编写一个程序，用于枚举 n 个数 x1, x2, …, xn 的所有排列方式（即全排列枚举）。如果两种排列方式的前 k-1 个数相同，则将第 k 个数序号更小的排列放在前面。例如，当 n=3 且 x={100, 20, 5} 时，应该按以下顺序输出结果：{100, 20, 5}, {100, 5, 20}, {20, 100, 5}, {20, 5, 100}, {5, 100, 20}, {5, 20, 100}。

Input

​ 第一行是一个正整数 n。第二行是 n 个正整数，x1, x2, …, xn。

Output

​ 输出n！行，每行显示一个排列，排列应按题目要求的顺序排列。

解题思路：

​ 套用回溯经典模板，使用一个used数组记录该元素的使用记录，每次从0开始循环，将每次的元素存到res数组中，当res的长度和原数组长度相等时，就输出全排列。

代码：

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
#include <bits/stdc++.h>
using namespace std;

vector<int> res;
vector<int> used(10000, 0);

void dfs(vector<int> nums, int k){
    if(res.size() == k){
        for(int j = 0; j < k; j++){
            cout << res[j] << ' ';
        }
        cout << endl;
        return;
    }
    for(int i = 0; i < nums.size(); i++){
        if(!used[i]){
            res.push_back(nums[i]);
            used[i] = 1;
            dfs(nums, k);
            used[i] = 0;
            res.pop_back();
        }
    }
}

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    dfs(nums, nums.size());
    return 0;
}

额外-全排列2

题目：

​ 编写一个程序，用于枚举 n 个数 x1, x2, …, xn 的所有排列方式（即全排列枚举）。如果两种排列方式的前 k-1 个数相同，则将第 k 个数序号更小的排列放在前面。例如，当 n=3 且 x={100, 20, 5} 时，应该按以下顺序输出结果：{100, 20, 5}, {100, 5, 20}, {20, 100, 5}, {20, 5, 100}, {5, 100, 20}, {5, 20, 100}。注意：数组中可能有重复数字。

解题思路：

​ 思路与全排列相同，多了一个特判条件，即把整个数组排序，used数记录使用情况，遇到重复数字就跳过。

1
2
3
4
// 特判条件
if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false){
    continue;
}

代码：

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
#include <bits/stdc++.h>
using namespace std;

vector<int> res;
vector<int> used(10000, 0);
vector<vector<int>> ress;

void dfs(vector<int> nums, int k){
    if(res.size() == k){
        ress.push_back(res);
        return;
    }
    for(int i = 0; i < nums.size(); i++){
        if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false){
            continue;
        }
        if(!used[i]){
            res.push_back(nums[i]);
            used[i] = 1;
            dfs(nums, k);
            used[i] = 0;
            res.pop_back();
        }
    }
}

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    sort(nums.begin(), nums.end());
    dfs(nums, nums.size());
    return 0;
}

4.2 其他经典回溯问题

p8003-n皇后问题

题目：

Description

​ 在一个 n×n 的国际象棋棋盘上，需要放置 n 个皇后，使得每一行、每一列以及每条对角线上最多只有一个皇后。这就构成了 n 皇后问题。例如，当 n=8 时，八皇后问题就是在 8×8 的棋盘上放置八个皇后，遵循上述规则。

​ 你的任务是根据给定的 n，输出 n 皇后问题的前 k 个解。由于每一行必定只有一个皇后，如果两个解的前 k-1 行的皇后位置相同，那么在第 k 行中皇后位置更靠左的解应排在前面（即按字典序排序）。

Input

​ 输入只有一行，包含两个正整数 n 和 k，表示需要求解的是 n 皇后问题的前 k 个解。

Output

​ 输出前 k 个解：每行包含 n 个用空格隔开的正整数，依次表示每组解中第 1, 2, …, n 行的皇后所在的列位置。

解题思路：

​ 套用回溯模板，利用数组下标索引当做行，元素当列，减少数组使用空间。外层循环代表横着的遍历，dfs代表向竖着的向下方遍历，每次都从0开始循环，通过available找到合适的解。每当res数组等于棋盘的长度时，就得到正确答案，输出数组。

代码：

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
#include <bits/stdc++.h>
using namespace std;

vector<int> res;
int cnt = 0;

bool available(int column){
    int row = res.size();
    for(int i = 0; i < res.size(); i++){
        if(row-i == column-res[i] || row+column == i+res[i] || column == res[i]){
            return false;
        }
    }
    return true;
}

void dfs(int n, int k){
    if(res.size() == n){
        cnt++;
        for(int j = 0; j < res.size(); j++){
            cout << res[j]+1 << ' ';
        }
        cout << endl;
        if(cnt == k){
             exit(0);
        }
        return;
    }
    for(int i = 0; i < n; i++){
        if(available(i)){
            res.push_back(i);
            dfs(n, k);
            res.pop_back();
        }
    }
}

int main(int argc, char const *argv[])
{
    int n, k;
     // 关闭输入输出缓存，使效率提升
	ios::sync_with_stdio(false);
	// 解除cin和cout的默认绑定，来降低IO的负担使效率提升
	cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k;
    dfs(n, k);
    return 0;
}

p8004-01背包

题目：

Description

​ 给定 N件物品和一个容量为 V 的背包。每件物品只能使用一次。

​ 第i件物品的体积是vi，价值是wi。

​ 你的任务是决定将哪些物品装入背包，以使得这些物品的总体积不超过背包容量，同时总价值最大。请输出最大价值。

Input

  • 第一行包含两个整数，分别为N和V，表示物品数量和背包容量。
  • 接下来的 N 行，每行包含两个整数vi和wi，表示第i件物品的体积和价值。

Output

​ 输出一个整数，表示最大价值

解题思路：

​ 套用回溯模板，拿一个maxValue记录最大的value，每次加入了weight之后都更新一次maxvalue，直到得到最大的value，其实这个和求子集差不多，只是多了一个把每个子集求和的步骤。

代码：

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
#include <bits/stdc++.h>
using namespace std;

int maxValue = 0;
int allVolume = 0;
int allValue = 0;

void dfs(int v, int n, int startIndex, vector<int> weight, vector<int> value){
    // if(allVolume > v){
    //     return;
    // }
    for(int i = startIndex; i < n; i++){
        if(allVolume+weight[i] <= v){
            allVolume += weight[i];
            allValue += value[i];
            maxValue = max(maxValue, allValue);
            dfs(v, n, i+1, weight, value);
            allVolume -= weight[i];
            allValue -= value[i];
        }
    }
}

int main(int argc, char const *argv[])
{
    int n, v;
    cin >> n >> v;
    vector<int> weight(n);
    vector<int> value(n);
    for(int i = 0; i < n; i++){
        cin >> weight[i] >> value[i];
    }
    dfs(v, n, 0, weight, value);
    cout << maxValue;
    return 0;
}

5.分支限界

p8011-走迷宫

题目：

Description

  • 一个n×m的二维整数数组表示迷宫。数组中包含的元素只有0

    和1：

    • 0表示这个位置是可以走的路径。
    • 1表示这个位置是不可通过的墙壁。

  • 数组的起始位置(1,1)（左上角）和结束位置(n,m)（右下角）的元素保证为0。

  • 迷宫至少存在一条从起点到终点的通路。

Input

  • 第一行两个整数n，m，其中1 ≤ n, m ≤ 100
  • 接下来的n行，每行m个整数,只有0和1，中间用空格隔开

Output

  • 输出一个整数，表示从左上角(1,1)到右下角(n,m)的最少移动次数

解题思路：

直接用广度优先搜索按层扩散就可以。这里可以设计一个visit数组记录已经访问过的结点，避免重复搜索。步骤如下：

  1. 定义迷宫：将迷宫表示为一个二维矩阵，其中墙壁用障碍物表示（通常用1表示），可以通过的路径用通道表示（通常用0表示）。
  2. 定义BFS函数：创建一个BFS函数，用于搜索迷宫路径。该函数应接受起始位置和目标位置作为参数。
  3. 初始化队列和访问状态：创建一个队列，用于存储待访问的位置。同时，创建一个额外的二维矩阵，用于记录每个位置的访问状态。
  4. 将起始位置加入队列，并将其标记为已访问。
  5. 开始BFS：进入一个循环，直到队列为空为止。
  6. 弹出队首位置：从队列中取出一个位置。
  7. 检查是否到达目标位置：检查当前位置是否为目标位置，如果是，则表示找到了迷宫路径，可以结束搜索。
  8. 获取相邻位置：获取当前位置的所有相邻位置（上、下、左、右）。
  9. 检查相邻位置的合法性：对于每个相邻位置，检查其是否越界、是否为障碍物，以及是否已经访问过。如果是非法位置，则跳过。
  10. 标记相邻位置：将合法的相邻位置标记为已访问，并将其加入队列。
  11. 重复步骤 6-10，直到队列为空。
  12. 如果搜索结束时仍未找到目标位置，则表示迷宫中没有可达的路径。

代码：

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
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;

struct Node
{
    int x, y, step;
    Node(int xx, int yy, int stepp){
        x = xx;
        y = yy;
        step = stepp; // 记录当前是第几层，即第几步。
    }
};

int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int bfs(vector<vector<int>> nums, int n, int m){
    vector<vector<int>> visit(n, vector<int>(m, 0));
    queue<Node> q;
    q.push(Node(0, 0, 0));
    visit[0][0] = 1;
    while(!q.empty()){
        Node cur = q.front();
        q.pop();
        // 遍历朝四个方向走
        for(int i = 0; i < 4; i++){
            int x = cur.x + d[i][0];
            int y = cur.y + d[i][1];
            if(x == n-1 && y == m-1){
                return cur.step+1;
            }
            if(x >= 0 && x < n && y >= 0 && y < m && visit[x][y] == 0 && nums[x][y] == 0){
                q.push(Node(x, y, cur.step+1));
                visit[x][y] = 1;
            }
        }
    }
    return -1;
}



int main(int argc, char const *argv[])
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> nums(n, vector<int>(m, 0));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> nums[i][j];
        }
    }
    int res = bfs(nums, n, m);
    cout << res;
    return 0;
}

p8012-0-1背包

题目：

Description

​ 给定 N 件物品和一个容量为 V 的背包。每件物品只能使用一次。

​ 第i件物品的体积是vi，价值是wi。

​ 你的任务是决定将哪些物品装入背包，以使得这些物品的总体积不超过背包容量，同时总价值最大。请输出最大价值。

Input

  • 第一行包含两个整数，分别为N和V，表示物品数量和背包容量。
  • 接下来的 N 行，每行包含两个整数vi和wi，表示第i件物品的体积和价值。

Output

​ 输出一个整数，表示最大价值。

解题思路：

​ 分支限界：利用某种情况能够得到的上限value值进行剪枝。

​ 必要框架：node结构体（存储该情况下的总价值、总重量，以及bound（分支限界中的关键变量，该变量可以求到该情况下的理论最大价值，将其与之前情况得到的实际value比，如果比他大，就可以继续，如果比他小，那么这一部分bfs就被剪枝掉），一个<重载函数，）、node类型的优先队列，利用node里面的<重载函数,使得在计算的时候可以优先计算出实际的最大value，后面的情况就可以直接剪枝、bfs函数，首先初始化一个cur，没有实际含义，相当于链表中的头结点，方便之后的循环，根据题意，进行bfs，该题的bfs有两种情况，将该元素放入or不放入背包，两种情况都进行一些判断然后决定是否放入背包，再进行下一层。

代码：

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
using namespace std;

int n, v;
struct Item{
    double weight;
    double value;
    // 一个weight有多少value
    double density;
};

struct Node{
    int index; // 索引，记录到第几层了。
    int totalweight; // 现在这种情况的weight和，即背包已经使用了的容量
    int totalvalue; //  现在得到的最大value值
    int upperbound; // 这种情况下最终的理论value最大值。
    // upperbound越大的排在前面
    bool operator < (const Node& a) const{
        return upperbound < a.upperbound;
    }
};

// 平均value最大的排前面，因为根据贪心得知，以最小的weight可以得到最大的alue
bool cmp(const Item& a, const Item& b){
    return a.density > b.density;
}

// 求出该种装背包方法的理论最大value值。
double bound(int index, double totalweight, double totalvalue, vector<Item> nums){
    int i = index;
    while(i < n && totalweight + nums[i].weight <= v){
        totalweight += nums[i].weight;
        totalvalue += nums[i].value;
        i++;
    }
    if(i < n)
        totalvalue += (v-totalweight) * (nums[i].density);
    return totalvalue;
}

int bfs(vector<Item> nums){
    // 初始化cur和q
    priority_queue<Node> q;
    Node t1, t2, cur;
    int maxvalue = 0;
    cur.index = -1;
    cur.totalweight = 0;
    cur.totalvalue = 0;
    cur.upperbound = bound(0, 0, 0, nums);
    q.push(cur);
    // bfs
    while(!q.empty()){
        cur = q.top();
        q.pop();
        int index = cur.index+1;
        if(index >= n){
            continue;
        }
        // 情况1：选择放入背包
        if(cur.totalweight + nums[index].weight <= v){
            t1.totalweight = cur.totalweight + nums[index].weight;
            t1.totalvalue = cur.totalvalue + nums[index].value;
            t1.index = index;
            t1.upperbound = bound(index+1, t1.totalweight, t1.totalvalue, nums);
            maxvalue = max(maxvalue, t1.totalvalue);
            // 因为这一次相比于上一次的情况是多放进了一个物品，
            // 那么他的上界肯定要么会增加， 要么不变，所以不用判断。
            q.push(t1);
        }
        // 情况2：选择不放入背包。
        t2.totalweight = cur.totalweight;
        t2.totalvalue = cur.totalvalue;
        t2.index = index;
        t2.upperbound = bound(index, cur.totalweight, cur.totalvalue, nums);
        // maxvalue = max(maxvalue, t2.totalvalue);
        // 剪枝，如果理论最大值比现在已有的实际value最大值还大，这种情况就可以继续走下去，否则就不走了。
        if(t2.upperbound > maxvalue){
            q.push(t2);
        }
    }
    return maxvalue;
}

int main(int argc, char const *argv[])
{

    cin >> n >> v;
    vector<Item> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i].weight >> nums[i].value;
        nums[i].density = (double)nums[i].value / nums[i].value;
    }
    sort(nums.begin(), nums.end(), cmp);
    cout << bfs(nums);
    return 0;
}

p8013-任务分配

题目：

Description

​ 假设有 ( n ) 个任务和 ( n ) 个人。每个人完成每个任务所需的时间都是不同的。你的任务是分配每个人恰好一个任务，以使完成所有任务的总时间最小。

Input

  • 第一行包含一个整数n,（1 <= n <= 20），表示任务和人的数量。
  • 接下来的n行，每行包含n个整数，表示完成任务的时间矩阵。第i行第j个整数表示第i个人完成第j个任务所需的时间。

Output

  • 输出一个整数，表示最小的完成所有任务所需的总时间。

解题思路：

​ 该题思路与p8002差不多，记住三个重要结构：node，包含当前最低时间花费、理论最终最小时间花费，任务是否被分配标记数组等。bound，求出当前情况下的理论最终最小时间花费，方便剪枝。bfs，首先初始化cur，然后for循环一行，即每个人的不同任务，遇到可以的就入队，不可以的就剪枝或跳过。

代码：

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;

int n, ans = INT_MAX;
vector<vector<int>> nums(n, vector<int>(n, 0));

struct Node{
    int index; // 代表已经到第i个人了
    vector<int> used; // 第i个任务是否被分配
    vector<int> task; // 第索引个人分配了第j个任务
    int cost; // 该种情况已经花费的时间
    int lowerbound; // 该种情况理论的最低花费时间
    bool operator < (const Node& b) const {
        return lowerbound > b.lowerbound; //越小的越优先出队 
    }
};
// 求该种情况理论的最低花费时间
int bound(Node node){
    int temp = node.index;
    int mintime = INT_MAX;
    int minsum = node.cost;
    for(int i = temp+1; i < n; i++){
        for(int j = 0; j < n; j++){
            if(node.used[j] == 0){
                mintime = min(mintime, nums[i][j]);
            }
        }
        minsum += mintime;
    }
    return minsum;
}

void bfs(){
    Node cur, t1;
    // 初始化，相当于头结点，等会方便循环
    // 优先队列将理论花费时间最少的数据放前面先出队计算
    priority_queue<Node> q;
    cur.index = -1;
    cur.used.resize(n);
    cur.task.resize(n);
    cur.cost = 0;
    cur.lowerbound = bound(cur);
    q.push(cur);
    while(!q.empty()){
        cur = q.top();
        q.pop();
        for(int j = 0; j < n; j++){
            if(cur.used[j] == 1){
                continue;
            }
            else{
                // t1是cur的下一层
                t1.index = cur.index+1;
                t1.used = cur.used;
                // 将第j个任务标记为用过
                t1.used[j] = 1;
                t1.task = cur.task;
                // 标记第t1.index个人分配了第j个任务
                t1.task[t1.index] = j;
                // 更新时间花费
                t1.cost = cur.cost + nums[t1.index][j];
                t1.lowerbound = bound(t1);
                // ans记录实际最低花费时间，如果理论最低花费时间都比ans大，那么直接剪枝，反之入队继续计算
                if(t1.lowerbound < ans){
                    // 任务都分配完了，记录实际最低花费时间
                    if(t1.index == n-1){
                        ans = min(t1.cost, ans);
                    }
                    else{
                        q.push(t1);
                    }
                }
            }
        }
    }
}

int main(int argc, char const *argv[])
{
    cin >> n;
    nums.resize(n, vector<int>(n));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++)
            cin >> nums[i][j];
    }
    bfs();
    cout << ans << endl;
    return 0;
}

6.递归

p1002-最大公约数

题目：

Description

给定两个正整数a和b，请写一个函数来计算它们的最大公约数。

Input

输入包含两个正整数a和b，分别在一行上，用空格隔开。

Output

输出一个正整数，表示a和b的最大公约数

解题思路：

​ 该题的关键就是运用辗转相除法，问题解决过程中不用管a和b谁大，对于gcd函数递归中的参数，一定记牢！如果要求最小公倍数的话，将每个数除以最大公约数再相乘再乘上最大公约数即可。

代码：

1
2
3
4
5
6
7
8
int gcd(int a, int b){
    if(b == 0){
        return a;
    }
    else{
        return gcd(b, a%b);
    }
}

p3001-n的阶乘

题目：

Description

​ 给定一个正整数 n，计算其阶乘 n!。n的阶乘定义为从1到 n 的所有正整数的乘积。即： n! = 1 * 2 * 3 * … * n

挑战：
不使用任何循环语句（如：for、while）

Input

  • 输入仅包含一个正整数 (n)。

Output

  • 输出一个正整数，表示 (n!)。

解题思路：

​ 简单递归，注意这里需要用long long，int会越界。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
// 注意这里需要用long long，int会越界
long long factorial(int n){
    if(n == 1){
        return 1;
    }
    else{
        return n * factorial(n-1);
    }
}

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    cout << factorial(n);
    return 0;
}

p3002-递归剪枝求斐波那契数列

题目：

Description

​ 斐波那契数列是一个非常著名的数列，它的定义如下：

  • F(0) = 0

  • F(1) = 1

  • F(n) = F(n-1) + F(n-2) ，其中 ( n > 1 )

    给定一个正整数 n ( 1 <= n <=50 )，请你计算出第 n 个斐波那契数列的值。

Input

  • 输入仅包含一个正整数 ( n )。

Output

  • 输出一个正整数，表示第 ( n ) 个斐波那契数的值。

解题思路：

​ 设置一个a数组，a[i]代表第i个数的值，每次计算都记录一下对应的值，实现剪枝操作。

代码：

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 <bits/stdc++.h>
using namespace std;
// 拿一个数组
long long a[100] = {0};
long long Fibonacci(int n){
    if(n == 0 || n == 1){
        return n;
    }
    else if(a[n] != 0){
        return a[n];
    }
    else{
        a[n] = Fibonacci(n-1) + Fibonacci(n-2);
        return a[n];
    }
}

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    cout << Fibonacci(n);
    return 0;
}

p3006-天平平衡问题

题目：

Description

​ 你有n个重量不同的砝码和一个天平, 每个砝码可以放在天平的左盘或者右盘或者不放.

​ 砝码重量为w1,w2,…,wn

​ 问有多少种放置砝码的方式，使得天平平衡?

​ 两边均为空，均不放砝码，也算一种方案。

Input

​ 第1行, 1个正整数 n

​ 第2行, n 个正整数w1,w2,…,wn, 以空格分隔

Output

​ 天平平衡的放置方案数

解题思路：

​ 同样也是简单递归，遍历所有可能出现的情况。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
int res = 0;
void average(vector<int> nums, int index, int leftSum, int rightSum){
    if(index == nums.size()){
        if(leftSum == rightSum){
            res++;
        }
        return;
    }
    average(nums, index+1, leftSum + nums[index],rightSum);
    average(nums, index+1, leftSum,rightSum + nums[index]);
    average(nums, index+1, leftSum, rightSum);
}

7.数学问题

p1004-质数判断

题目：

Description

​ 编写一个程序，从用户那里接收一个正整数n，并判断该数字是否为质数。

Input

​ 输入只有一行，包含一个正整数n (1 < n < 10^7) 。

Output

  • 如果n是质数，则输出 “Yes”
  • 如果n不是质数，则输出 “No”

解题思路：

​ 记住6这一数字，我们可以把所有的数表示为6i，6i+1，6i+2，6i+3，6i+4，6i+5，而在这些数中只有6i+1和6i+5可能是质数，其他均不可能是质数。所以我们可以以6为基准进行计算。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool isPrime(int num){
    if(num == 1 || num == 4){
        return false;
    }
    else if(num == 2 || num == 3){
        return true;
    }
    else if(num % 6 != 1 && num % 6 != 5){
        return false;
    }
    // 只需要判断到平方根，因为一个数要有约数的话，一定有一个比平方根大和一个比平方根小的约数。
    // 由于下方有判断i-1的条件，如果是i <= sqrt(num)的话，那么可能i-1就取不到，所以要取大一个的数。
    for(int i = 6; i <= sqrt(num)+1; i+=6){
        if(num % (i-1) == 0 || num % (i+1) == 0){
            return false;
        }
    }
    return true;
}

p3005-求第k小的数

题目：

Description

​ 给定一个包含 ( n ) 个正整数的数组，找出其中不重复的第 ( k ) 个最小整数。

Input

  • 第一行输入两个正整数 ( n ) 和 ( k )，分别表示数组的大小和要查询的第k小的数。其中 ( 1 <= n <= 10^4 )，( 1 <= k <= 10^3 )。
  • 第二行输入 ( n ) 个正整数，表示数组中的元素。每个整数的值均小于 ( 3 * 10^4 )，整数之间用空格分隔。

Output

​ 输出第 ( k ) 个最小的不重复整数。

​ 如果不存在第 ( k ) 个这样的整数，则输出NO RESULT。

解题思路：

​ 经典的（快速）排序+set集合思想算出。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void quickSort(vector<int>& nums, int k,int left, int right){
    if(left >= right){
        return;
    }
    int x = nums[left];
    int i = left, j = right;
    while(i < j){
        while(i < j && nums[j] >= x) j--;
        if(j >= left && i < j) nums[i++] = nums[j];
        while(i < j && nums[i] < x)  i++;
        if(i <= right && i < j)  nums[j--] = nums[i];
    }
    nums[i] = x;
    quickSort(nums, k, left, i-1);
    quickSort(nums, k, i+1, right);
}

8.模拟

p2003-回字形矩阵

题目：

Description

给定一个正整数 (n)，请你生成一个 (n * n) 的回字形矩阵。

回字形矩阵的特点是：

  1. 矩阵的最外一圈的数字都是1。
  2. 次外一圈的数字都是2。
  3. 以此类推，直到矩阵中心。

如果 (n) 为偶数，那么最内圈的数字是 (n/2)。如果 (n) 为奇数，那么最内圈的数字是 (n/2 + 1)。

Input

一个正整数 (n) (1 <= n <= 100)，表示矩阵的大小

Output

输出一个 (n * n) 的回字形矩阵。每行包含 (n) 个用空格隔开的整数

解题思路：

​ 此题采用碰壁转向，即到了该转弯的位置就进行转弯，相似的题还有力扣上的螺旋矩阵，回旋矩阵等。

代码：

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
   int x = 0, y = 0, row, column, dx = 0, dy = 1;
// 这里是判断在哪个位置结束循环。
   if(n % 2 == 0){
       row = n/2;
       column = row-1;
   }
   else{
       row = n/2;
       column = row;
   }
   int count = 1;
// 这里是碰壁转向的通用模板
   while(x != row || y != column){
       num[x][y] = count;
       if (dy == 1 && (y >= n - 1 || num[x][y+1] != 0))
       {
           dx = 1;
           dy = 0;
       }
       else if (dx == 1 && (x >= n - 1 || num[x+1][y] != 0))
       {
           dx = 0;
           dy = -1;
       } 
       else if (dy == -1 && (y <= 0 || num[x][y-1] != 0))
       {
           dx = -1;
           dy = 0;
       } 
       else if (dx == -1 && (x <= 0 || num[x-1][y] != 0))
       {
           dx = 0;
           dy = 1;
           count += 1;
       }
       x += dx;
       y += dy;

   }
   num[row][column] = count;

p2014-约瑟夫环

题目：

Description

​ n 个人围成一圈，从第一个人开始报数,数到 m 的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

Input

输入两个整数 n,m。 (1<= m,n <=100)

Output

输出一行 n 个整数，按顺序输出每个出圈人的编号。

解题思路：

​ 建立一个vector数组，到指定位置就erase掉需要删除的数据，每次加上m就取余。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n, m;
    cin >> n >> m;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        nums[i] = i+1;
    }
    int temp = 0;
    while(nums.size()){
        temp = (temp + m - 1) % nums.size();
        int x = nums[temp];
        nums.erase(nums.begin()+temp);
        cout << x << ' ';
    }
    return 0;
}

9.栈

p2015-表达式括号匹配

题目：

Description

​ 编写一个程序，用于检测一个包含小写英文字母、运算符（+、-、*、/）和括号的数学表达式的括号是否正确匹配。表达式以@符号结束。你的任务是判断在表达式中的括号是否正确匹配。

  • 如果括号正确匹配（每个左括号都有一个相应的右括号，并且它们的顺序是正确的），输出YES。
  • 如果括号不匹配，则输出NO。

Input

  • 输入包含一行，即要检查的表达式。表达式的长度小于 255 个字符，并且包含少于 20 对括号。

Output

  • 输出包含一行，是YES或NO，表示括号是否正确匹配

解题思路：

​ 使用栈来简化括号匹配的检测。栈先入后出特点恰好与本题括号排序特点一致，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；

​ 建立哈希表 dic 构建左右括号对应关系：key左括号，value右括号；这样查询 2个括号是否对应只需 O(1)时间复杂度；建立栈 stack，遍历字符串 s 并按照算法流程一一判断。

20. 有效的括号 - 力扣（LeetCode）

代码：

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
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    string s;
    cin >> s;
    stack<char> stk;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '('){
            stk.push('(');
        }
        else if(s[i] == ')'){
            if(!stk.empty()){
                stk.pop();
            }
            else{
                cout << "NO";
                exit(0);
            }
        }
    }
    if(stk.empty()){
        cout << "YES";
    }
    else{
        cout << "NO";
    }
    return 0;
}

10.双指针

p3023-移动数组中的零

题目：

Description

​ 给定一个数组nums，将所有0移动到数组的末尾，同时保持非零元素的相对顺序。

​ 必须在不复制数组的情况下原地对数组进行操作。

Input

  • 第一行：一个整数n，表示数组的元素个数。
  • 第二行：n个整数。

Output

  • 移动后的数组，元素间用空格隔开。

解题思路：

​ 双指针（将i置于要赋值的位置，将j处的值赋给i）+减少cin的时间.

代码：

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
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int n;
    ios_base::sync_with_stdio(false);
	cin.tie(0);
    cin >> n;
    vector<int> res(n);
    for (int i = 0; i < n; i++) {
        cin >> res[i];
    }
    int i = 0, j = 0;
    // while(res[i] != 0 && i < res.size()){
    //     i++;
    // }
    // j = i+1;
    // while(res[j] == 0 && j < res.size()){
    //     j++;
    // }
    while(i < res.size() && j < res.size()){
        if(res[j] != 0){
            res[i] = res[j];
            i++;
            // j++;
        }
        j++;
    }
    while(i < res.size()){
        res[i] = 0;
        i++;
    }
    for(int x: res){
        cout << x << ' ';
    }
    return 0;
}

p3024-最长连续不重复子序列

题目：

Description

​ 给定一个长度为n的正整数序列，请找出最长的不包含重复数的连续子序列，并输出其长度。

Input

  • 第一行包含一个整数n。
  • 第二行包含n个整数，表示整数序列。

Output

  • 共一行，包含一个整数，表示最长的不包含重复数的连续子序列的长度。

解题思路：

​ 双指针+map，一个指针记录长度左边的位置，一个记录右边的位置，利用map记录每个数字出现的次数，大于1就将i往右移。

代码：

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
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{

    int n;
    cin >> n;
    vector<int> res(n);
    for (int i = 0; i < n; i++) {
        cin >> res[i];
    }
    // set<int> mySet(res.begin(), res.end());
    // cout << mySet.size();
    map<int, int> mp;
    int num = 0, i = 0, j = 0;
    int sum = 0;
    while(i < n && j < n){
        mp[res[j]]++;
        while(mp[res[j]] > 1){
            mp[res[i]]--;
            i++;
        }
        sum = max(sum, j-i+1);
        j++;
    }
    cout << sum;
    return 0;
}

11.前缀和

p3025-和为k的子数组

题目：

Description

​ 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

Input

  • 第一行：一个整数 (n)，表示数组的元素个数。
  • 第二行：(n) 个整数，表示数组的元素。
  • 第三行：一个整数 (k)。

Output

  • 输出一个整数，表示和为k的连续子数组的个数。

解题思路：

​ map+前缀和，每次求一个前缀和时，都去遍历map里面的前缀和看是否有符合要求的。此题有一个细节就是mp[0]=1，因为当sum=k时，这个前缀和没有被记录，所以需要单独列一个出来加上。

代码：

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
#include <bits/stdc++.h>
using namespace std;
// 前缀和
int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    int k;
    cin >> k;
    map<int, int> mp;
    int sum = 0;
    int count = 0;
    // 由于下方可能k会等于0，或者第一次出现sum=k的情况，但是这个是没有被记录的，所以首先需要令mp[0]=1
    mp[0] = 1;
    for(int i = 0; i < n; i++){
        sum += nums[i];
        if(mp.find(sum-k) != mp.end()){
            count += mp[sum-k];
        }
        mp[sum]++;
    }
    cout << count;
    return 0;
}

一些小知识点

1.set里面是去重并自动进行了排序的

2.减少cin的时间的两行代码:

1
2
ios_base::sync_with_stdio(false);
cin.tie(0);

3.在出现wrong answer的时候可以考虑将int类型改成long long类型，可能是溢出了。

4.出现runtime error可以考虑数组溢出等问题。