UVA 1508 Equipment ( DFS )

UVa Online Judge
題目大意是給 n ≤ 10000個五元組，求取 k個的情況下每個位置的最大值相加的值最大。
感覺就只能暴搜，但五元組數量太多，裸裸的 2^10000剪枝也沒有希望。想一下，浪費時間是因為其實真正會用到的五元組不多，更仔細想想，會用到的定義是將用到的那些格子封鎖，確定為最大值，所以實際上我們可以對那五元做枚舉。對於每個五元組，生成其所有子集表示哪些會當作是最大值，然後預處理出取五元組中的每個子集最好可以得到多少分。接下來就能用暴搜，每次至少少去原本五元中一元，複雜度大大進步。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 4;

int bit(int x){ return 1 << x; }
int bitcount(int x){ return x == 0 ? 0 : bitcount( x >> 1 ) + ( x & 1 ); }

int n, k;
int r[MAXN][5];

int sum[MAXN][1 << 5];
int mxsum[1 << 5];

int dfs(int took, int S, int v){
    if( took == k ) return v;
    int best = 0;
    for(int S0 = S; S0 > 0; S0 = ( S0 - 1 ) & S)
        best = max<int>( best, dfs( took + 1, S - S0, v + mxsum[S0] ) );
    return best;
}

void solve(){
    for(int i = 0; i < n; ++i){
        memset( sum[i], 0, sizeof(sum[i]) );
        for(int j = 0; j < bit( 5 ); ++j)
            for(int g = 0; g < 5; ++g)
                if( j & ( 1 << g ) )
                    sum[i][j] += r[i][g];
    }
    for(int j = 0; j < bit( 5 ); ++j){
        mxsum[j] = 0;
        for(int i = 0; i < n; ++i)
            mxsum[j] = max<int>( mxsum[j], sum[i][j] );
    }
    int ans = dfs( 0, bit( 5 ) - 1, 0 );
    printf("%d\n", ans);
}

int main(){
    int T; scanf("%d", &T);
    while( T-- ){
        scanf("%d%d", &n, &k);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < 5; ++j)
                scanf("%d", &r[i][j]);
        solve();
    }
    return 0;
}