[SCOI2005]最大子矩阵解题报告

题目描述

这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。

输入输出格式

输入格式

第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。

输出格式：

只有一行为k个子矩阵分值之和最大为多少。

input

3 2 2
1 -3
2 3
-2 3

output

9

思路：

显然这道题是一道与矩阵有关的DP，所以可以用一种叫 悬线法 的奇技淫巧，所谓悬线法就是先把每一行，每一列的状态都给拓展出来，然后再变为矩阵进行合并。

先求出前缀和，方便转移，然后就是转移了。

wait!!

有没有注意到m<=2??

当m=1时，很简单。

f[i][k]=max(f[i][k],f[j][k-1]+sum[1][i]-sum[1][j]);//代表在前i个数中
//分成k个所取得的最大值

当m=2时，就要用悬线法啦！F[i][j][k]代表在第一行取i个，第二行取j个，分成k个的最大值。什么都不做，先拓展第一行，然后第二行，最后合并。

for(int k=1;k<=K;k++)
          for(int i=1;i<=n;i++)
              for(int j=1;j<=n;j++)
              {
                  F[i][j][k]=max(F[i-1][j][k],F[i][j-1][k]);//不在这一个点取数
                  for(int l=0;l<i;l++) //拓展第一行
                      F[i][j][k]=max(F[i][j][k],F[l][j][k-1]+sum[1][i]-sum[1][l]);
                  for(int l=0;l<j;l++)//拓展第二行
                      F[i][j][k]=max(F[i][j][k],F[i][l][k-1]+sum[2][j]-sum[2][l]);
                  if(i==j)//i==j时就是一个矩阵啦，要合并了。
                      for(int l=0;l<i;l++)
                          F[i][j][k]=max(F[i][j][k],
                                  F[l][l][k-1]+sum[1][i]-sum[1][l]+sum[2][j]-sum[2][l]);
              }

应该都懂了吧？？

完整代码

#include<bits/stdc++.h>
using namespace std;
#define maxn 105
#define INF 0x3f3f3f

int n,m,K,x;
int f[maxn][maxn];
int F[maxn][maxn][maxn];
int sum[4][maxn];

int main()
{
    scanf("%d%d%d",&n,&m,&K);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&x),sum[j][i]=sum[j][i-1]+x;//前缀和
    if(m==1)
    {
        //memset(f,-INF,sizeof(f));
        for(int k=1;k<=K;k++)
            for(int i=1;i<=n;i++)
            {
                f[i][k]=f[i-1][k];
                for(int j=0;j<i;j++)
                    f[i][k]=max(f[i][k],f[j][k-1]+sum[1][i]-sum[1][j]);
            }
        printf("%d\n",f[n][K]);
        return 0;
    }
    else
    {
        //memset(F,-INF,sizeof(F));
        for(int k=1;k<=K;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                {
                    F[i][j][k]=max(F[i-1][j][k],F[i][j-1][k]);
                    for(int l=0;l<i;l++) 
                        F[i][j][k]=max(F[i][j][k],F[l][j][k-1]+sum[1][i]-sum[1][l]);
                    for(int l=0;l<j;l++)
                        F[i][j][k]=max(F[i][j][k],F[i][l][k-1]+sum[2][j]-sum[2][l]);
                    if(i==j)
                        for(int l=0;l<i;l++)
                            F[i][j][k]=max(F[i][j][k],
                                    F[l][l][k-1]+sum[1][i]-sum[1][l]+sum[2][j]-sum[2][l]);
                }
        printf("%d\n",F[n][n][K]);
    }
    return 0;
}

祝各位dalao成功AC!!!

最后安利一波dalao的博客
T大佬
L大佬
LV大佬
LDY大佬