首先对于m==1的情况非常容易处理（其实这儿因为边界我错了好久。。。），直接DP就好了，设f[i][k]为这个矩阵前i个选k个矩阵的最大和，那么f[i][k]=max(f[j][k-1]+sum[j+1][i])，那么对于m==2的时候类似与m=1的时候，设w[i][j][k]为左面的一行前i个中，右面的一行前j个中，一共选k个矩阵能选取得最大矩阵。

　　那么转移也比较明显，有一下几种转移

　　w[i][j][k]=max(w[i-1][j][k],w[i][j-1][k])这种情况代表什么都不选。

　　w[i][j][k]=max(w[ii][j][k-1]+sum[ii+1][i][0])这种情况代表在左面一行重新确定i这个位置如何选取。

　　类似的w[i][j][k]=max(w[i][jj][k-1]+sum[jj+1][j][1])这种情况代表在右面一行重新确定i这个位置如何选取。 

　　当i==j的时候w[i][j]=max(w[ii][ii]+sum[ii+1][i][2])，这样就代表选了一个占两行的矩形，然后注意枚举的边界就可以了。

　　反思：开始我的想法是w[i][k]代表两行矩阵前i个选k个矩阵的最大值，我们可以知道选取矩阵的方法肯定是若干段只选取一行的组合，然后由选取两行的隔开，那么我们可以枚举i代表在i出选取占两行的矩形（这个矩形的长可以为0），那么w[i][k]=max(w[j][k]+f[j+1][ii]+sum[ii][i])，这个转移就是先枚举上一次的断点，然后后枚举上一断点到i的情况，就是一段只选取一行的加上一个占两行的最大值，那么首先要处理每一行的f[i][j][k]值，代表i,j段选取k个矩阵的最大值。后来因为转移的时候枚举边界特别麻烦，没有调出来，再仔细想想之后发现这种转移由于状态数太少，没办法准确的表达每一个状态，所以转移起来非常麻烦，所以就加了一维，可以准确的表达所有状态，而且转移十分方便，复杂度也降低了一个k（因为上一种方法需要枚举左右两行各选多少矩形），总之，还是自己太弱了。。。

　　

/**************************************************************    Problem: 1084    User: BLADEVIL    Language: C++    Result: Accepted    Time:88 ms    Memory:1672 kb****************************************************************/ //By BLADEVIL#include 
     
      #include 
      
       #include 
       
        #define maxn 100#define maxm 20 using namespace std; int n,m,k;int a[maxn][maxn],sum[maxn][maxn],f[maxn][maxm],w[maxn][maxn][maxm]; int main(){    scanf("%d%d%d",&n,&m,&k);    sum[0][1]=sum[0][2]=0;    for (int i=1;i<=n;i++)         for (int j=1;j<=m;j++)             scanf("%d",&a[i][j]),sum[i][j]=sum[i-1][j]+a[i][j];    if (m==1){        memset(f,0,sizeof(f));        for (int i=1;i<=n;i++) {            f[i][0]=0;            for (int l=1;l<=k;l++){                f[i][l]=f[i-1][l];                for (int j=0;j