SJTU OJ
========

AC题目编号及解答：`SJTU_OJ source <https://github.com/yyccli/SJTU_OJ>`_

- :ref:`1002-label`
- :ref:`1006-label`

.. _1002-label:

1002.二哥种花生
---------------

题目地址 `1002`_

.. _1002: https://acm.sjtu.edu.cn/OnlineJudge/problem/1002

*二哥在自己的后花园里种了一些花生，也快到了收获的时候了。这片花生地是一个长度为L、宽度为W的矩形，每个单位面积上花生产量都是独立的。他想知道，对于某个指定的区域大小，在这么大的矩形区域内，花生的产量最大会是多少。*

这道题理解题意之后就是一道典型的二维前缀和相关的题目。有关前缀和的相关题目与介绍可以参见：

- `前缀和太好用了 <http://aiifabbf.github.io/posts/prefix-sum/index.html>`_

- `前缀和的推广 <http://aiifabbf.github.io/posts/generic-prefix-sum.html>`_

介绍的非常详细，并包括很多开拓的思维。

题目本身很好理解，在一个二维数组中，给定一个大小，求解在该大小下数组中最大的那一块区域。
老样子，如果是使用暴力求解，时间复杂度应该会到达 :math:`O(n^4)` ，两个外层循环遍历出所有可能
的起始位置（也就是框定大小的左上角坐标），两个内层循环计算出该框定区域的和，最后比较大小得出结果。
暴力解最后还是超时了。（虽然知道要超时但是还是会提交一下xD）

解决办法就是在读入数据的时候构建该二维数组的二维前缀和，然后依然是两个外层循环遍历所有的起始位置，
不过在计算每个具体的框定大小的和时只需要 :math:`O(1)` 时间，最后的时间复杂度能降到 :math:`O(n^2)` 。

.. code:: C++

    #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-label:

1006.求和游戏
-------------

题目地址 `1006`_

.. _1006: https://acm.sjtu.edu.cn/OnlineJudge/problem/1006

*石柱上有一排石头键盘，每个键上有一个整数。请你在键盘上选择两个键，使这两个键及其之间的键上的数字和最大。如果这个最大的和不为正，则输出“Game Over"。*

这道题理解后可变形为求解一数组中 **最大的连续子数组的和** ，其中子数组的 **长度必须大于一** 。
要求长度大于一的原因在于题目里提到了需要选择两个键。

如果没有后面这个子数组长度必须大于一的条件，这个问题是一个经典的动态规划问题，能够在 :math:`O(n)` 
时间内求解。

.. code:: C++

    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;
    }


这段代码对我影响很大，当时算法课上老师请了一位校队同学给我们讲解动态规划。 [#1006-f1]_ 那位同学的ppt中第一
道题目就是这个，那是我第一次看到这么优美的解法。

回到题目，最直接的解法可以暴力，通过三个循环来实现。首先通过两个循环遍历
得到所有可能的两个键，最后通过一个循环来求的两个键之间的数组元素和。总复杂度达到 :math:`O(n^3)` 。
当然这个暴力的解法也可以降到 :math:`O(n^2)` 。在输入元素的时候构建该数组的前缀和数组，则此时在
最后一次循环中求解两个键之间的元素和的操作可以在 :math:`O(1)` 的时间内完成。

假设在读入时已经构建了该数组的前缀和数组（前缀和数组从下标1开始计数，下标0的位置设定值为0，这样是
为了写递推式的时候方便一些），则：

.. code:: C++

    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;
            }
        }
    } 

提交结果最后还是超时了，看来需要在 :math:`O(n)` 的方法上改进一下以满足题目的要求。

2020.7.21最后还是A了这道题，也没去找别人的思路，直接在 :math:`O(n)` 的方法上改进了：

.. code:: C++

    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]这样的情况。 

.. rubric:: ---------------

.. [#1006-f1] 大二下学期的算法与程序设计课上，这个题也可以叫做“最大连续子序列”