FZU 2060 The Sum of Sub-matrices(状态压缩DP)

The Sum of Sub-matrices

Description

Seen draw a big 3*n matrix , whose entries Ai,j are all integer numbers ( 1 <= i <= 3, 1 <= j <= n ). Now he selects k sub-matrices( each Aij only belong one sub-matrices ), hoping to find the largest sum of sub-matrices’ elements.

Input

There are multiple test cases.

For each test case, the first line contains an integer n, k (1 <= n <= 100, 1 <= k <= 5, 3 * n >= k). The next three lines with n integers each gives the elements of the matrix ( | Ai,j | <= 10000).

Output

For each test case, print one line with an integer.

Sample Input

5 3

1 2 -10 3 5

3 -2 -10 2 -10

-10 -10 1 -10 -10

 

 

2 3

-1 -2

-3 -4

2 3

Sample Output

14

4

求3*n的矩阵里面的 k个子矩阵的最大和。

对列进行状态压缩

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <algorithm>

using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
const int mod = 1e9+7;
const int N = 105 ;
const int M = 13;
#define X first
#define Y second

int st1[M] = { 0 , 1 , 2 , 4 , 3 , 5 , 6 , 7 , 8 , 16 , 12 , 17 , 32 };
int st2[M] = { 0 , 1 , 2 , 4 , 3 , 5 , 6 , 7 , 3 , 6 , 7 , 7 , 7 };
int num[M] = { 0 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 1 , 1 , 2 , 2 , 1 };
int A[3][N] , dp[N][6][M] , n , k ;

int Sum( int colum , int st ) {
    int res = 0 ;
    for( int i = 0 ; i < 3 ; ++i ) if( st&(1<<i) )res += A[i][colum];
    return res ;
}

void Run() {
    memset( dp , 0x80 , sizeof dp ) ;
    dp[0][0][0] = 0;

    for( int i = 0 ; i < 3 ; ++i )
        for( int j = 1 ; j <= n ; ++j )
            cin >> A[i][j];

    for( int i = 1 ; i <= n ; ++i ) {
        for( int cs = 0 ; cs < M ; ++cs ) {
            for( int ps = 0 ; ps < M ; ++ps ) {
                int w = Sum(i,st2[cs]);
                for( int k1 = 0 ; k1 <= k ; ++k1 ) {
                    int low = num[cs] , up = num[cs] ;
                    for( int z = 0 ; z < 6 ; ++z ) if( st1[cs] & st1[ps] &(1<<z) ) low--;
                    for( int k2 = low ; k1 + k2 <= k && k2 <= up ; ++k2 ){
                        dp[i][k1+k2][cs] = max( dp[i][k1+k2][cs] , dp[i-1][k1][ps] + w );
                    }
                }
            }
        }
    }
    cout << *max_element( dp[n][k] , dp[n][k]+M ) << endl ;
}

int main(){
    #ifdef LOCAL
        freopen("in.txt","r",stdin);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while( cin >> n >> k )Run();
}