UVA1508 Equipment

(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))
好的，那么状态转移方程也就显而易见

    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 ", 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 ", dfs (31, p)) ;
}
}
return 0 ;
}