本文共 1283 字，大约阅读时间需要 4 分钟。

[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??

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

当m=2时

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

应该都懂了吧？？

完整代码

#include
   
    using namespace std;#define maxn 105#define INF 0x3f3f3fint 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
   

祝各位dalao成功AC!!!

最后安利一波dalao的博客

转载地址：http://wyuci.baihongyu.com/