bzoj1084: [SCOI2005]最大子矩阵ITeye - 牛牛娱乐

bzoj1084: [SCOI2005]最大子矩阵ITeye

2019年02月27日15时13分51秒 | 作者: 觅云 | 标签: 状况,评论,代码 | 浏览: 614

m =2,分m1和m2的状况评论,,然后就是一道水DP题,搬运见代码

const int N = 110;
int n, m, k, dat[2][N];
int S[4][N];
int f[N][N] = {0};
inline void sol1() {
 For(i, 1, k)
 For(j, 1, n) {
 f[i][j] = f[i][j - 1];
 For(l, 0, j - 1)
 f[i][j] = max(f[i][j], f[i - 1][l] + S[1][j] - S[1][l]);
 printf("%d\n", f[k][n]);
int F[N][N][N] = {0};
inline void sol2() {
 For(i, 1, k)
 For(j, 1, n)
 For(l, 1, n) {
 F[i][j][l] =
 max(F[i][j - 1][l - 1], max(F[i][j - 1][l], F[i][j][l - 1]));
 For(p, 0, j - 1)
 F[i][j][l] = max(F[i][j][l], F[i - 1][p][l] + S[1][j] - S[1][p]);
 For(p, 0, l - 1)
 F[i][j][l] = max(F[i][j][l], F[i - 1][j][p] + S[2][l] - S[2][p]);
 if(j  l)
 For(p, 0, l - 1)
 F[i][j][l] = max(F[i][j][l], F[i - 1][p][p] + S[3][l] - S[3][p]);
 printf("%d\n", F[k][n][n]);
int main() {
 SetIO("1084");
 scanf("%d%d%d", n, m, 
 For(i, 1, 3)
 For(j, 1, n) S[i][j] = 0;
 For(i, 1, n) {
 For(j, 1, m)
 scanf("%d", dat[i][j]), S[j][i] = S[j][i - 1] + dat[i][j];
 S[3][i] = S[1][i] + S[2][i];
 if(m  1) sol1();
 else sol2();
 return 0;
}

 

 

版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表牛牛娱乐立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章