BZOJ 1084: [SCOI2005]最大子矩阵

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
题解
代码

Description

这里有一个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

题解

水DP，就是f[k][i][j]表示第一行到i第二行到j已经取了k个的最大受益！M=1时就是只是用i，j中的一个就好了。

代码

#include<cstdio>
using namespace std;
int f[15][105][105];
int s[105][5];
int N,M,K;
int Ans;
inline int remax(int a,int b){return (a>b?a:b);}
inline void solution_1(){
    for (int i=1;i<=N;i++) s[i][1]+=s[i-1][1];
    for (int k=1;k<=K;k++){
        for (int ed=1;ed<=N;ed++){
            f[k][ed][1]=f[k][ed-1][1];
            for (int st=0;st<ed;st++){
                f[k][ed][1]=remax(f[k-1][st][1]+s[ed][1]-s[st][1],f[k][ed][1]);
            }
        }
    }
    Ans=f[K][N][1];
}
inline void solution_2(){
    for (int i=1;i<=N;i++){
        s[i][1]+=s[i-1][1];
        s[i][2]+=s[i-1][2];
    }
    for (int k=1;k<=K;k++)
        for (int upEd=1;upEd<=N;upEd++)
        for (int doEd=1;doEd<=N;doEd++){
            f[k][upEd][doEd]=remax(f[k][upEd][doEd-1],f[k][upEd-1][doEd]);
            for (int st=0;st<upEd;st++)
                f[k][upEd][doEd]=remax(f[k][upEd][doEd],f[k-1][st][doEd]+s[upEd][1]-s[st][1]);
            for (int st=0;st<doEd;st++)
                f[k][upEd][doEd]=remax(f[k][upEd][doEd],f[k-1][upEd][st]+s[doEd][2]-s[st][2]);
            if (upEd==doEd)
            for (int st=0;st<upEd;st++)
                f[k][upEd][doEd]=remax(f[k][upEd][doEd],f[k-1][st][st]+s[upEd][1]-s[st][1]+s[doEd][2]-s[st][2]);
        }
    Ans=f[K][N][N];
}
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",&s[i][j]);
    switch(M){
        case 1:
            solution_1();
            break;
        case 2:
            solution_2();
            break;
    }
    printf("%d\n",Ans);
    return 0;
}

#include<cstdio>

using namespace std;

int f[15][105][105];

int s[105][5];

int N,M,K;

int Ans;

inline int remax(int a,int b){return (a>b?a:b);}

inline void solution_1(){

for (int i=1;i<=N;i++) s[i][1]+=s[i-1][1];

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

for (int ed=1;ed<=N;ed++){

f[k][ed][1]=f[k][ed-1][1];

for (int st=0;st<ed;st++){

f[k][ed][1]=remax(f[k-1][st][1]+s[ed][1]-s[st][1],f[k][ed][1]);

}

Ans=f[K][N][1];

}

inline void solution_2(){

for (int i=1;i<=N;i++){

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

s[i][2]+=s[i-1][2];

}

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

for (int upEd=1;upEd<=N;upEd++)

for (int doEd=1;doEd<=N;doEd++){

f[k][upEd][doEd]=remax(f[k][upEd][doEd-1],f[k][upEd-1][doEd]);

for (int st=0;st<upEd;st++)

f[k][upEd][doEd]=remax(f[k][upEd][doEd],f[k-1][st][doEd]+s[upEd][1]-s[st][1]);

for (int st=0;st<doEd;st++)

f[k][upEd][doEd]=remax(f[k][upEd][doEd],f[k-1][upEd][st]+s[doEd][2]-s[st][2]);

if (upEd==doEd)

for (int st=0;st<upEd;st++)

f[k][upEd][doEd]=remax(f[k][upEd][doEd],f[k-1][st][st]+s[upEd][1]-s[st][1]+s[doEd][2]-s[st][2]);

}

Ans=f[K][N][N];

}

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",&s[i][j]);

switch(M){

case 1:

solution_1();

break;

case 2:

solution_2();

break;

}

printf("%d\n",Ans);

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑