BZOJ-1084: [SCOI2005]最大子矩阵(DP)

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1084

开始是以为是什么神题，后来发现m<=2那就直接DP O（n^3）水掉了。。。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

#define rep( i , x )for(int i =0; i ++< x ;)

#define Rep( i , x )for(int i =0; i < x ;++ i )

 

const int maxn =110, maxm =3, maxk =15;

 

int n , m , k ;

 

 

void solve0(  ){

    int a[ maxn ], sum[ maxn ], f[ maxn ][ maxk ];

    bool u[ maxn ][ maxk ];

    sum[0]=0;

    rep( i , n ){

        scanf("%d", a + i );

        sum[ i ]= sum[ i -1]+ a[ i ];

    }

    memset( f ,0,sizeof( f ));

    memset( u ,false,sizeof( u ));

    u[0][0]=true;

    rep( i , n )Rep( j , k +1){

        if( u[ i -1][ j ]){

            u[ i ][ j ]=true, f[ i ][ j ]= f[ i -1][ j ];

        }

        if( j )Rep( x , i )if( u[ x ][ j -1]){

            u[ i ][ j ]=true;

            f[ i ][ j ]=max( f[ i ][ j ], f[ x ][ j -1]+ sum[ i ]- sum[ x ]);

        }

    }

    int ans =0;

    rep( i , n )if( u[ i ][ k ]) ans =max( ans , f[ i ][ k ]);

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

}

 

int a[ maxn ][ maxm ], sum[ maxn ][ maxm ], f[ maxn ][ maxn ][ maxk ];

bool u[ maxn ][ maxn ][ maxk ];

 

void solve1(  ){

    sum[0][1]= sum[0][2]=0;

    rep( i , n ){

        scanf("%d%d",&a[ i ][1],&a[ i ][2]);

        sum[ i ][1]= sum[ i -1][1]+ a[ i ][1];

        sum[ i ][2]= sum[ i -1][2]+ a[ i ][2];

    }

    memset( f ,0,sizeof( f ));

    memset( u ,false,sizeof( u ));

    u[0][0][0]=true;

    Rep( i , n +1)Rep( j , n +1)if( i || j ){

        Rep( h , k +1){

            if( i )if( u[ i -1][ j ][ h ]){

                u[ i ][ j ][ h ]=true;

                f[ i ][ j ][ h ]= f[ i -1][ j ][ h ];

            }

            if( j )if( u[ i ][ j -1][ h ]){

                u[ i ][ j ][ h ]=true;

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

            }

            if( h ){

                Rep( x , i )if( u[ x ][ j ][ h -1]){

                    u[ i ][ j ][ h ]=true;

                    f[ i ][ j ][ h ]=max( f[ i ][ j ][ h ], f[ x ][ j ][ h -1]+ sum[ i ][1]- sum[ x ][1]);

                }

                Rep( y , j )if( u[ i ][ y ][ h -1]){

                    u[ i ][ j ][ h ]=true;

                    f[ i ][ j ][ h ]=max( f[ i ][ j ][ h ], f[ i ][ y ][ h -1]+ sum[ j ][2]- sum[ y ][2]);

                }

                if( i == j )Rep( x , i )if( u[ x ][ x ][ h -1]){

                    u[ i ][ j ][ h ]=true;

                    f[ i ][ j ][ h ]=max( f[ i ][ j ][ h ], f[ x ][ x ][ h -1]+( sum[ i ][1]- sum[ x ][1])+( sum[ j ][2]- sum[ x ][2]));

                }

            }

        }

    }

    int ans =0;

    Rep( i , n +1)Rep( j , n +1)if( u[ i ][ j ][ k ]){

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

    }

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

}

 

int main(  ){

    scanf("%d%d%d",&n ,&m ,&k );

    if( m ==1)solve0(  );else solve1(  );

    return 0;

}