最大子段和
题目描述
给出一个长度为 $n$ 的序列 $a$，选出其中连续且非空的一段使得这段和最大。
思路
简单的前缀和 + 递推，用$a[i]$记录到第$i$个位置时与$i$相连续的最大值，用$ans$记录字段和的最大值
转移方程a[i] = max(x, a[i - 1] + x)， ans = max(a[i], ans)
代码
void solve(){
int n;
cin >> n;
vector<int>a(n);
int ans = -INF;
int x;
for (int i = 0; i < n; i++) {
cin >> x;
if (i == 0){
a[i] = x;
} else{
a[i] = max(x, a[i - 1] + x);
ans = max(a[i], ans);
}
}
cout << ans << endl;
}
地毯
题目描述
在 $n\times n$ 的格子上有 $m$ 个地毯。
给出这些地毯的信息，问每个点被多少个地毯覆盖。
输入格式 第一行，两个正整数 $n,m$。意义如题所述。
接下来$m$ 行，每行两个坐标 $(x_1,y_1)$ 和 $(x_2,y_2)$，代表一块地毯，左上角是 $(x_1,y_1)$，右下角是 $(x_2,y_2)$。
输出格式 输出 $n$ 行，每行 $n$ 个正整数。
第 $i$ 行第 $j$ 列的正整数表示 $(i,j)$ 这个格子被多少个地毯覆盖。
$n, m \leqslant 1000$
思路
差分
复习
何为差分
假设我们现在要给[2,5]这个区间加一。
原来的序列是：
0 0 0 0 0 0 0 0这时候我们在2上面打 +1 标记， 6 上面打 -1 标记。
那么现在的序列是：
0 +1 0 0 0 -1 0这样的话，从左往右扫描这个数组，记录当前经过的标签之和，这个和就是那个数对应的答案
这样，对于每个区间加操作，只需要$O(1)$的时间打上标记， 最后扫描输出即可
现在把问题拓展到二维。假设我们要覆盖$[(2,2),(5,5)]$ ，那么标记便可以这样打：
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 0 0 0 0 0
即在每一行都按照一维的方式来操作：
for (int j = x1; j <= x2; j++) {
cf[j][y1]++;
cf[j][y2 + 1]--;
}
这样一来,打标记时候的复杂度为$O(n)$,总复杂度为$O(mn + n^2)$
代码
int cf[2000][2000];
void solve(){
int n, m;
cin >> n >> m;
int x1, y1, x2, y2;
for (int i = 0; i < m; i++) {
cin >> x1 >> y1 >> x2 >> y2;
for (int j = x1; j <= x2; j++) {
cf[j][y1]++;
cf[j][y2 + 1]--;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cf[i][j] += cf[i][j - 1];
cout << cf[i][j] << " ";
}
cout << endl;
}
}
海底高铁
题目描述
一个铁路经过$N$个城市，每个城市一个站，但不能直达，只能相邻城市的一段铁路单独买票
对于一段铁路$i$，连接了城市$i$和城市$i+ 1$，有两种买票方式。
-
单独购买纸质票，价格为$A_i$
-
买卡，只需要花工本费$C_i$，每次通行花费$B_i（B_i < A_i )$
现在一个人要出差去$M$个城市，按照$P_i$的顺序访问，可能会多次访问一个城市，且相邻访问的城市位置不一定相邻，而且不会是同一个城市。
求总费用的最小值
$M，N \leqslant 10^5, A_i,B_i,C_i \leqslant 10 ^ 5$
思路
前缀和和差分数组结合， 对于其中一小段，我们要么全部买纸票，要么全部刷卡。
所以问题拆分成了统计每一小段经过的总次数，再在两种费用方案之间取最小值
后者不难，此题的考点在前者，直接暴力统计会绎演顶证，鉴定为纯纯的$TLE$
因此先用差分数组预处理每次要去的起点和终点，打上标记。
然后再求每一项的前缀和，这样最后前缀和数组就是每一段铁路的经过次数了
例：如果我们要经过$1-3$ 和 $2-4$
先打上标记
+1 -1 +1 +1 -1 -1
- - - - - -- - - -- - -- -- - -- --
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
图1 图2 图3
再进行前缀和
1 2 2 1 0
- - - - -
1 2 3 4 5
图4
更多细节见代码
代码
void solve(){
int n, m;
cin >> n >> m;
vector<ll>p(n + 2);//station
vector<ll>cnt(n + 2);//count
for (int i = 1; i <= m; i++) {
cin >> p[i];
}
ll ma, mi;
for (int i = 1; i <= m - 1; i++) {
ma = max(p[i], p[i + 1]);
mi = min(p[i], p[i + 1]);
cnt[ma]--;//因为第i段铁路是从第i连到第i+1个城市，所以减去ma就是减去第ma-1 +1段铁路
cnt[mi]++;
}
for (int i = 1; i <= n; i++) {//WA了一发，开始的range是[1,m]
cnt[i] += cnt[i - 1];//这就是为什么前缀和处理的话数组下标要从1开始
}
int a, b, c;
ll ans = 0;
for (int i = 1; i <= n - 1; i++) {
cin >> a >> b >> c;
ans += min(a * cnt[i], b * cnt[i] + c);
}
cout << ans << endl;
}
最大加权矩形
题目描述
一个$N \times N$的矩阵，矩阵里每个点有对应的权值，求子矩阵权值和的最大值
$N \leqslant 120$
思路
一眼二维前缀和，数据范围很小，直接用$O(n^4)$的复杂度莽过去了。
但二维前缀和的公式还是不熟
二维矩阵的前缀和（到0，0点的）:
$$f[i][j] = f[i][j - 1] + f[i -1][j] - f[i - 1][j - 1] + a[i][j]$$ 子矩阵的和从$(i，j)$到$(k，l)$ $O(n^4)$： $$f[k][l] - f[k][j - 1] - f[i - 1][l] + f[i - 1][j - 1]$$
代码 （$O(n^4)$）
int a[125][125], f[125][125];
void solve(){
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
f[i][j] = f[i][j - 1] + f[i -1][j] - f[i - 1][j - 1] + a[i][j];
}
}
int ans = -INF;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int l = i; l <= n; l++) {
for (int i1 = j; i1 <= n; i1++) {
ans = max(f[l][i1] - f[l][j - 1] - f[i - 1][i1] + f[i - 1][j - 1], ans);
}
}
}
}
cout << ans << endl;
}
优化版
思路
我们可以考虑将矩形压缩成一维，比如处理一个2行的矩形时，将a [ i ][ j ]与a [ i - 1 ][ j ]相加，成为一个新的数组f [ n ]，再使用上述代码进行动态规划，找出局部最优解。
首先进行前缀和，这样可以用减法来快速表示压缩的矩形。
可以模拟一下，a[ i ][ j ] - a[ i - k ][ j ]正好是以i为最下面一行，往上k行的压缩结果，这就很方便地表示了压缩后的矩形。
那再次循环，运用第一个代码的简单变形，可以求出以i为最下一行，向上k行的矩形最大值，多次更新ans就行
代码
void solve2(){
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
a[i][j] += a[i - 1][j]; // 前缀和处理
}
}
int ans = -INF;
int f1[150] = {0}, dp[150] = {0};
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= i; k++) {
for (int j = 1; j <= n; j++) {
f1[j] = a[i][j] - a[i - k][j];
dp[j] = max(dp[j - 1] + f1[j], f1[j]);
ans = max(ans, dp[j]);
}
}
}
cout << ans << endl;
}
这是前一种方法的速度
这是后一种的
可以看出来优化还是十分明显的
领地选择
题目描述
首都被认为是一个占地 $C \times C$ 的正方形。小 Z 希望你寻找到一个合适的位置，使得首都所占领的位置的土地价值和最高。
思路
与上一题的第一种方法类似，使用二位前缀和预处理，然后$O(n^2)$扫一遍即可
代码
int a[1005][1005];
int f[1005][1005];
void solve(){
int n, m, c;
cin >> n >> m >> c;
int ma = -INF;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
f[i][j] = f[i][j - 1] + f[i - 1][j] - f[i - 1][j - 1] + a[i][j];
}
}
int x, y;
for (int i = c; i <= n; i++) {
for (int j = c; j <= m; j++) {
if (f[i][j] - f[i][j - c] - f[i - c][j] + f[i - c][j - c] > ma){
ma = f[i][j] - f[i][j - c] - f[i - c][j] + f[i - c][j - c];
x = i - c + 1;
y = j - c + 1;
}
}
}
cout << x << " " << y << endl;
}
光骓者的荣耀
题目描述
小 K 为了关心人民生活，决定定期进行走访。他每一次会从 $1$ 号城市到 $n$ 号城市并在经过的城市进行访问。其中终点必须为城市 $n$。
不仅如此，他还有一个传送器，传送半径为 $k$，也就是可以传送到 $i-k$ 和 $i+k$。如果目标城市编号小于 $1$ 则为 $1$，大于 $n$ 则为 $n$。
但是他的传送器电量不足，只能传送一次，况且由于一些原因，他想尽量快的完成访问，于是就想问交通部部长您最快的时间是多少。
思路
先前缀和预处理，然后以区间大小为$k$扫一遍求传送的最大值即可
（92分坑）：在求区间和最大值的时候，下标不要从1开始，因为cnt[i + k] - cnt[i]如果从1开始的话会忽略cnt[1]本身的值
代码
void solve(){
int n, k;
cin >> n >> k;
vector<ll>a(n);
vector<ll>cnt(n);
for (int i = 1; i < n; i++) {
cin >> a[i];
}
partial_sum(all(a),cnt.begin());
ll ans = -1;
for (int i = 0; i < n - k; i++) {
ans = max(ans, cnt[i + k] - cnt[i]);
}
cout << cnt[n - 1] - ans << endl;
}