bzoj1084[SCOI2005]最大子矩阵

bzoj1084[SCOI2005]最大子矩阵

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

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

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

Sample Input 3 2 2 1 -3 2 3 -2 3 Sample Output 9 设dp[i][j][k]表示第一列匹配到i 第二列 匹配到j 现在一共有k个子矩阵 求最大的答案 首先假设当前我不选 我直接把答案继承过来 如果我选的话 我枚举我选第一列的某段 或者枚举我选第二列的某段 然后最后再枚举一下 我这两列合成一个子矩阵选的最优情况

#include#include#include#define N 110using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}int n,m,k,s[3][N],d[N],dp[N][N][12],f[N][12];int main(){ freopen("bzoj1084.in","r",stdin); n=read();m=read();k=read(); for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) s[j][i]=s[j][i-1]+read(); for (int i=1;i<=n;++i) d[i]=s[1][i]+s[2][i]; for (int i=1;i<=n;++i){ for (int j=1;j<=n;++j){ for (int z=1;z<=k;++z){ dp[i][j][z]=max(dp[i-1][j][z],dp[i][j-1][z]); for (int i1=0;i1

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。