SJTU OJ¶
AC题目编号及解答：SJTU_OJ source
1002.二哥种花生¶
题目地址 1002
二哥在自己的后花园里种了一些花生，也快到了收获的时候了。这片花生地是一个长度为L、宽度为W的矩形，每个单位面积上花生产量都是独立的。他想知道，对于某个指定的区域大小，在这么大的矩形区域内，花生的产量最大会是多少。
这道题理解题意之后就是一道典型的二维前缀和相关的题目。有关前缀和的相关题目与介绍可以参见：
介绍的非常详细，并包括很多开拓的思维。
题目本身很好理解，在一个二维数组中，给定一个大小，求解在该大小下数组中最大的那一块区域。 老样子，如果是使用暴力求解，时间复杂度应该会到达 \(O(n^4)\) ，两个外层循环遍历出所有可能 的起始位置（也就是框定大小的左上角坐标），两个内层循环计算出该框定区域的和，最后比较大小得出结果。 暴力解最后还是超时了。（虽然知道要超时但是还是会提交一下xD）
解决办法就是在读入数据的时候构建该二维数组的二维前缀和，然后依然是两个外层循环遍历所有的起始位置， 不过在计算每个具体的框定大小的和时只需要 \(O(1)\) 时间，最后的时间复杂度能降到 \(O(n^2)\) 。
#include<iostream>
#include<memory.h>
using namespace std;
#define MAX 1001
int arr[MAX][MAX];
int map[MAX][MAX];
int main() {
int l, w;
cin >> l >> w;
for (int i = 1; i <= l; i++) {
for (int j = 1; j <= w; j++) {
cin >> arr[i][j];
}
}
int a, b;
cin >> a >> b;
int m = 0;
memset(map, 0, sizeof(map));
for (int i = 1; i <= l; i++) {
for (int j = 1; j <= w; j++) {
map[i][j] = map[i - 1][j] + map[i][j - 1] - map[i - 1][j - 1] + arr[i][j];
if (i >= a && j >= b) {
m = m > map[i][j] - map[i - a][j] - map[i][j - b] + map[i - a][j - b] ? m : map[i][j] - map[i - a][j] - map[i][j - b] + map[i - a][j - b];
}
}
}
//int temp;
//for (int p = 0; p < l - a + 1; p++) {
// for (int q = 0; q < w - b + 1; q++) {
// temp = 0;
// for (int x = 0; x < a; x++) {
// for (int y = 0; y < b; y++) {
// temp += arr[p + x][q + y];
// }
// }
// m = temp > m ? temp : m;
// }
//}
cout << m;
return 0;
}
裂墙推荐去看上面的链接。
1006.求和游戏¶
题目地址 1006
石柱上有一排石头键盘，每个键上有一个整数。请你在键盘上选择两个键，使这两个键及其之间的键上的数字和最大。如果这个最大的和不为正，则输出“Game Over”。
这道题理解后可变形为求解一数组中 最大的连续子数组的和 ，其中子数组的 长度必须大于一 。 要求长度大于一的原因在于题目里提到了需要选择两个键。
如果没有后面这个子数组长度必须大于一的条件，这个问题是一个经典的动态规划问题，能够在 \(O(n)\) 时间内求解。
int solve(int *a, int len) {
int ans = -INF, dp = 0;
for(int i = 0; i < len; i++){
if(dp > 0) {
dp += a[i];
}
else{
dp = a[i];
}
if(dp > ans){
ans = dp;
}
}
return ans;
}
这段代码对我影响很大，当时算法课上老师请了一位校队同学给我们讲解动态规划。 [1] 那位同学的ppt中第一 道题目就是这个，那是我第一次看到这么优美的解法。
回到题目，最直接的解法可以暴力，通过三个循环来实现。首先通过两个循环遍历 得到所有可能的两个键，最后通过一个循环来求的两个键之间的数组元素和。总复杂度达到 \(O(n^3)\) 。 当然这个暴力的解法也可以降到 \(O(n^2)\) 。在输入元素的时候构建该数组的前缀和数组，则此时在 最后一次循环中求解两个键之间的元素和的操作可以在 \(O(1)\) 的时间内完成。
假设在读入时已经构建了该数组的前缀和数组（前缀和数组从下标1开始计数，下标0的位置设定值为0，这样是 为了写递推式的时候方便一些），则：
int solve(int *a, int len){ // 这里传前缀和数组进来
int ans = -INF, t = 0;
for(int i = 1; i < len; i++){
for(int j = i + 1; j <= len; j++){
// 计算下标为i到j（包含两端点）的子数组的和，可以在O(1)时间完成
t = a[j] - a[i - 1];
ans = t > ans ? t : ans;
t = 0;
}
}
}
提交结果最后还是超时了，看来需要在 \(O(n)\) 的方法上改进一下以满足题目的要求。
2020.7.21最后还是A了这道题，也没去找别人的思路，直接在 \(O(n)\) 的方法上改进了：
int solve(int *a, int len){
int ans = -INF, dp = 0, predp = 0;
for (int i = 0; i < len; i++) {
predp = dp;
if (dp > 0) {
dp += a[i];
ans = dp > ans ? dp : ans;
}
else {
dp = a[i];
if (dp > 0) {
ans = (dp + predp) > ans ? (dp + predp) : ans;
}
}
}
}
这一题的思路现在还是没法很好的系统的描述出来（但是代码能写出来），等过段时间看多了dp之后再回头 来看。
改进的主要思路是处理了可能出现 负 + 正 = 正 并做为结果的情况。例如输入[3, -6, 7]或者是 [-2, -1, 9]这样的情况。
—————