\(Translate\)

给出\(n\)个\(5\)元组，从中选出\(k\)组，使得在\(k\)组中\(5\)个位置，每个位置上最大数(在选择的\(k\)组中的最大值)之和最大，求这个和。

\(Input\)

(输入有多组数据) 第一行\(T\)为数据组数，每组数据的第一行为\(n,k\),接下来\(n(n<=10^5)\)行每行\(5\)列，表示\(n\)个五元组。

\(Output\)

对于每组数据，输出选出\(k\)个五元组中每五个位置上最大数之和的最大值。

\(Sample\)

$1 $

\(3 2\)

\(2 4 3 5 3\)

\(1 6 2 4 4\)

\(3 3 4 2 3\)

以上数据，在选择2、3行时为最优解，\(ans_{max}=3+6+4+4+4=21\)。

\(Solution\)

考虑这道题的范围，应该用\(DP\)求解，那么该怎么想呢？

我们先用一个数组\(maxx[i]\)来记录第\(i\)列的最大值，当\(k>=5\)时，显然每个位置的最大值一定能取到，这时一定是最优解。

但是出题人显然不会这么良心

但是这道题显然会有很多\(k<5\)的情况，这时候我们考虑用状态压缩\(dp\)，使用\(dp[i]\)表示在\(i\)状态下的答案，比如\(i=10010\)，则表示已经决定了第2、3、5列时的最大值，那么预处理的时候就要用\(dp[i]\)表示在\(i\)状态下全局能够取到的最大值，再逐步进行限制就可以了

那么怎么转移呢?枚举子集!，枚举子集的代码背过就行，是对当前可以选的部分枚举，代码大致是这样

for (int s0 = s ; s0 ; s0 = s & (s0 - 1))

好的，那么状态转移方程也就显而易见

int dfs (int s, int sum){ if (!sum) return 0 ; int tmp = 0 ; for (int s0 = s ; s0 ; s0 = s & (s0 - 1)) tmp = max (tmp, dp[s0] + dfs ((s0 ^ s), sum - 1)) ; return tmp ; }

好的那么问题来了，假如两个状态选择的行是同一行呢，这其实是不影响的，因为我们取得是最大值

\(Code\)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std ;const int N = 10005 ;int d[10], f[N][10], dp[35] ;int t, n, p ;int dfs (int s, int sum){    if (!sum) return 0 ;    int tmp = 0 ;    for (int s0 = s ; s0 ; s0 = s & (s0 - 1)) tmp = max (tmp, dp[s0] + dfs ((s0 ^ s), sum - 1)) ;    return tmp ;}int main (){    scanf ("%d", &t) ;    while (t--){        memset (d, 0, sizeof (d)) ;        scanf ("%d%d", &n, &p) ;        for (int i = 1 ; i <= n ; ++i)            for (int j = 0 ; j < 5 ; ++j){                scanf ("%d", &f[i][j]) ;                d[j] = max (d[j], f[i][j]) ;            }        if (p >= 5){            int res = 0 ;            for (int i = 0 ; i < 5 ; ++i) res += d[i] ;            printf ("%d\n", res) ;        }        else {            memset (dp, 0, sizeof (dp)) ;            for (int i = 1 ; i <= n ; ++i){                for (int j = 0 ; j <= 31 ; ++j){                    int tmp = 0 ;                    for (int k = 0 ; k < 5 ; ++k){                        if (j & (1 << k)) tmp += f[i][k] ;                        dp[j] = max (dp[j], tmp) ;                    }                }            }            printf ("%d\n", dfs (31, p)) ;        }    }    return 0 ;}