ACM寒假第六讲

一、最大子段和

设计思路

题目给定了一个长度为n的序列a，选出其中连续且非空的一段，并且使得这一段和最大。设计的思路是构造首先构造一个数组存放序列a，之后再次构造一个数组存放序列和累加的情况（考虑到前i个），并统计最大的累加情况（例如，add[1]表示第一个数，add[2]表示前两个数相加的和与add[1]之间较大得数的结果，以此比较下去），之后再进行最后判断就得出答案。

设计代码

#include <bits/stdc++.h>
using namespace std;
#define N 200001
#define INF 0x3f3f3f3f

int main() {
	int n, maxn = -INF;
	cin >> n;
	vector<int>a(n + 1), add(n + 1);
	for (int i = 1; i <= n; ++i)
		cin >> a[i];//读入
	for (int i = 1; i <= n; ++i)
		add[i] = max(a[i], a[i] + add[i - 1]);//第一次累加和的判断
	for (int i = 1; i <= n; ++i)
		maxn = max(maxn, add[i]);//第二次的判断
	cout << maxn;
	return 0;
}

二、采药

设计思路

题目要求设计一个程序，使其在限定时间内可以采到的草药价值最大。翻阅wiki可以得知，这是一个典型的背包问题，因此参考模板进行思考。首先设定数组存储草药，之后键入时间和价值，最后利用一个循环进行同步判断寻找即可

设计代码

#include <iostream>
using namespace std;

int main() {
	int M, T, time, value;
	cin >> T >> M;
	int f[10000] = {0};
	for (int i = 0; i < M; i++) {
		cin >> time >> value;
		for (int j = T; j >= time; j--) {
			f[j] = max(f[j], f[j - time] + value);//同步规划判断，f[j-time]表示减去此时间之后还剩的时间。
		}
	}
	cout << f[T];
	return 0;
}

三、宝物筛选

设计思路

题目和第二题类似，要求求出在采集车不超载的情况下收集的宝物的最大价值。不同之处在于，本题如果通过两层循环遍历并且进行同步查找，会超时，因此思路行不通。于是又去翻了翻文档，发现要对背包问题进行优化，于是进行下一步思考。需要设定多个背包函数进行优化操作，使得最后只需要一层循环即可解决。

设计代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000;
int f[maxn], V, n, c, w, m;

void zobag(int x, int y) {//0-1背包
	for (int i = V; i >= x; i --)
		f[i] = max(f[i], f[i - x] + y);
}

void completebag() {//完全背包
	for (int i = c; i <= V; i ++)
		f[i] = max(f[i], f[i - c] + w);
}

void mbag(int a, int b, int h) {//多重背包
	if (h * a >= V)
		completebag();
	else {
		int k = 1;
		while (k < h) {
			zobag(k *a, k *b);
			h -= k;
			k <<= 1;
		}
		zobag(h *a, h *b);
	}
}

int main() {
	cin >> n >> V;
	while (n --) {
		cin >> w >> c >> m;
		mbag(c, w, m);
	}
	cout << f[V] << endl;
	return 0;
}

四、最长公共子序列

设计思路

这个题目要求两个序列排列的最长公共子序列，在之前的题目中曾经见过，不过之前的题目序列输入都有结束，因此可以用指针来写，本题貌似不行。因此结合文档，综合考虑，可以使用二分查找和动态规划问题一起来进行。通过两个数组进行保存，进而把问题转换成求最长上升子序列的长度，之后套用模板即可。

设计代码

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int a[N], b[N], h[N], c[N];
int s[N], top;
int n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        h[a[i]] = i;//两层记录
    } 
    for(int i = 1; i <= n; i++)
    {
        cin >> b[i];
        c[i] = h[b[i]];//两层记录
    } 

    for(int i = 1; i <= n; i++)
    {
        if(top == 0 || s[top] < c[i]) s[++top] = c[i];
        else
        {
            int l = 1, r = top, ans = -1;
            while(l <= r)//二分查找
            {
                int mid = (l + r) >> 1;
                if(s[mid] >= c[i])
                {
                    ans = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            s[ans] = c[i];
        }
    }
    cout << top;

    return 0;
}

五、学习总结

在这次C++代码中，初步认识了动态规划的思路，虽然还不是很了解，只会套用模板而不是真正意义的融会贯通，不过还是对思路起到了一定意义上的扩充，之后还需要进一步消化。