首页 > 代码库 > 洛谷P2331 [SCOI2005] 最大子矩阵[序列DP]
洛谷P2331 [SCOI2005] 最大子矩阵[序列DP]
题目描述
这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。
输入输出格式
输入格式：
第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。
输出格式：
只有一行为k个子矩阵分值之和最大为多少。
输入输出样例
输入样例#1：
3 2 21 -32 3-2 3
输出样例#1：
9
m分类讨论
m=1，f[i][j]表示前i个选了j个矩阵
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=105,INF=1e9+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,m,K,a[N][3],d[N][15],s[N][3],ans=-INF;void dp1(){ for(int i=1;i<=n;i++) s[i][1]=s[i-1][1]+a[i][1]; for(int j=1;j<=K;j++) d[0][j]=-INF; for(int i=1;i<=n;i++) for(int j=1;j<=K;j++){ d[i][j]=d[i-1][j]; for(int z=0;z<i;z++) d[i][j]=max(d[i][j],d[z][j-1]+s[i][1]-s[z][1]); }}int f[N][N][15];void dp2(){ for(int i=1;i<=n;i++){ s[i][1]=s[i-1][1]+a[i][1]; //printf("s1 %d %d \n",i,s[i][1]); s[i][2]=s[i-1][2]+a[i][2]; //printf("s2 %d %d \n",i,s[i][2]); } for(int i=1;i<=max(n,m);i++) for(int j=1;j<=K;j++) f[i][0][j]=f[0][i][j]=-INF; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=K;k++){ f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]); for(int z=0;z<i;z++) f[i][j][k]=max(f[i][j][k],f[z][j][k-1]+s[i][1]-s[z][1]); for(int z=0;z<j;z++) f[i][j][k]=max(f[i][j][k],f[i][z][k-1]+s[j][2]-s[z][2]); if(i==j) for(int z=0;z<i;z++) f[i][j][k]=max(f[i][j][k],f[z][z][k-1]+s[i][1]-s[z][1]+s[i][2]-s[z][2]); //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=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read(); if(m==1) {dp1();printf("%d",d[n][K]);} else {dp2();printf("%d",f[n][n][K]);} //printf("\n\n%d",a[1][2]); return 0;}
洛谷P2331 [SCOI2005] 最大子矩阵[序列DP]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。