洛谷P2331 [SCOI2005] 最大子矩阵[序列DP]

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

m分类讨论
m=1，f[i][j]表示前i个选了j个矩阵 复杂度O(n*n*k)
m=2，f[i][j][k]表示第一行前i个第二行前j个选了k个矩阵，转移注意i==j可以上下都选
数据弱，随便一个全负的矩阵就把没初始化的卡住了

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long ll;

const int N=,INF=1e9+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m,K,a[N][],d[N][],s[N][],ans=-INF;

void dp1(){

    for(int i=;i<=n;i++)

        s[i][]=s[i-][]+a[i][];

    for(int j=;j<=K;j++) d[][j]=-INF;

    for(int i=;i<=n;i++)

        for(int j=;j<=K;j++){

            d[i][j]=d[i-][j];

            for(int z=;z<i;z++) d[i][j]=max(d[i][j],d[z][j-]+s[i][]-s[z][]);

        }

}

int f[N][N][];

void dp2(){

    for(int i=;i<=n;i++){

        s[i][]=s[i-][]+a[i][]; //printf("s1 %d %d \n",i,s[i][1]);

        s[i][]=s[i-][]+a[i][];    //printf("s2 %d %d \n",i,s[i][2]);

    }

    for(int i=;i<=max(n,m);i++) for(int j=;j<=K;j++) f[i][][j]=f[][i][j]=-INF;

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            for(int k=;k<=K;k++){

                f[i][j][k]=max(f[i-][j][k],f[i][j-][k]);

                for(int z=;z<i;z++) f[i][j][k]=max(f[i][j][k],f[z][j][k-]+s[i][]-s[z][]);

                for(int z=;z<j;z++) f[i][j][k]=max(f[i][j][k],f[i][z][k-]+s[j][]-s[z][]);

                if(i==j) for(int z=;z<i;z++)

                    f[i][j][k]=max(f[i][j][k],f[z][z][k-]+s[i][]-s[z][]+s[i][]-s[z][]);

                //printf("f %d %d %d %d\n",i,j,k,f[i][j][k]);

            }

}

int main(int argc, const char * argv[]) {

    n=read();m=read();K=read();

    for(int i=;i<=n;i++) for(int j=;j<=m;j++) a[i][j]=read();

    if(m==) {dp1();printf("%d",d[n][K]);}

    else {dp2();printf("%d",f[n][n][K]);}

    //printf("\n\n%d",a[1][2]);

    return ;

}