好久没更新牛客的博客了
更新一下下

链接：https://ac.nowcoder.com/acm/problem/20242
来源：牛客网

[SCOI2005]最大子矩阵
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。
注意：选出的k个子矩阵 不能相互重叠。
输入描述:
第一行为n,m,k（1 ≤ n ≤ 100,1 ≤ m ≤ 2,1 ≤ k ≤ 10），
接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。
输出描述:
只有一行为k个子矩阵分值之和最大为多少。
示例1
输入
复制
3 2 2
1 -3
2 3
-2 3
输出
复制
9

题目思路
看到这题思路是懵的。
但看一下m的范围好像就有了点起色。
当m为1时：最大k子段和
当m为2时：令第一列前i个与第二列前k个形成j个子矩阵的最大值
那么dp状态就很容易了：
可能新增的子矩阵是一列的，那么就是dp[st][k][p-1] + 第一列st~i的前缀和
如果增加第二列，与第一列同理
或者如果当i==p时此时可以将其合并
dp[st][st][p-1] + 两端前缀和
这里说一下，这么写的话无需考虑m=1或者m=2了，因为m=1时第二列全为0，对答案没有影响。

扩充一下：当m>2时可以考虑状压dp
改日补充一下 m>2的情况

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF=1e18;
const int maxn=1e6+6;
const int mod=1e9+7;
const double eps=1e-15;
inline bool read(ll &num)
{char in;bool IsN=false;
    in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll num[maxn];
ll f[maxn][3];
ll mp[105][3];
ll dp1[105][105];///0/1
ll dp[105][105][105];
int main(){
    read(n);read(m);read(p);
    for(int i=1;i<=n;i++){
        for(int k=1;k<=m;k++)
            read(mp[i][k]);
    }
    for(int k=1;k<=m;k++){
        for(int i=1;i<=n;i++){
            f[i][k] = f[i-1][k] + mp[i][k];
        }
    }
    ll ans = -INF;
    for(int i=1;i<=n;i++){
        for(int k=1;k<=n;k++){
            for(int j=1;j<=p;j++){
                dp[i][k][j] = max(dp[i-1][k][j],dp[i][k-1][j]);
                for(int st=0;st<i;st++)
                    dp[i][k][j] = max(dp[st][k][j-1]+f[i][1]-f[st][1],dp[i][k][j]);
                for(int st=0;st<k;st++)
                    dp[i][k][j] = max(dp[i][st][j-1]+f[k][2]-f[st][2],dp[i][k][j]);
                if(i==k){
                    for(int st=0;st<i;st++)
                        dp[i][k][j] = max(dp[st][st][j-1]+f[i][1]-f[st][1]+f[i][2]-f[st][2],dp[i][k][j]);

                    }
                }
        }
    }
    for(int i=1;i<=n;i++){
        for(int k=1;k<=n;k++){
            ans = max(ans,dp[i][k][p]);
        }
    }
    printf("%lld\n",ans);
    return 0;
}
/**
3
011
100
111
**/

这个代码写的有点麻烦了，将就看吧