G题 难度比较低的一道算法题

暴力可拿10% 复杂度 N M N M N * M ON6

二维差分可拿40% 复杂度 N M N * M ON4

矩阵压缩后跑最大序列和 可拿70% 复杂度 N N M ON3

矩阵旋转后矩阵压缩跑最大序列和 可拿满

为什么需要旋转矩阵呢?

因为矩阵压缩后跑最大序列和,复杂度是N N M，所以我们可以通过旋转矩阵，让N变小降低复杂度，但是结果不变

贴代码 
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<map>
#include<stack>
#include<list>

using namespace std;
list< int>jz[300000];
int ys[300000], jg, n, m;
int dpz[300000] = { 0 };
void dp()
{
    for (int i = 1; i <= m; ++i)
    {
        dpz[i]=0;
    }
    for (int i = 1; i <= m; ++i)
    {
        dpz[i] = max(dpz[i], ys[i] + dpz[i - 1]);
        jg = max(jg, dpz[i]);
    }
}
int main() {
    //freopen("9.in", " r ", stdin);
    //freopen("9.out", " w ", stdout);

    cin >> n >> m;
    if (n <= m) {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                int num;
                cin >> num;
                jz[i].push_back(num);
            }
        }
    }
    else {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                int num;
                cin >> num;
                jz[j].push_back(num);
            }
        }
        swap(n, m);
    }
    list<int>::iterator p1;
    for (int i = 1; i <= n; ++i)
    {
        memset(ys, 0, sizeof(ys));
        for (int j = i; j <= n; ++j)
        {
            p1 = jz[j].begin();
            for (int k = 1; k <= m; ++k, ++p1)
            {
                ys[k] += *p1;
            }
            dp();
        }
    }
    cout << jg;
}