\(Translate\)
给出\(n\)个\(5\)元组，从中选出\(k\)组，使得在\(k\)组中\(5\)个位置，每个位置上最大数(在选择的\(k\)组中的最大值)之和最大，求这个和。
(输入有多组数据) 第一行\(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 <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
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 ;
}
转载于:https://www.cnblogs.com/Liuz8848/p/10901179.html
相关资源：JAVA上百实例源码以及开源项目
