UVA1508Equipment(技巧枚举)

UVA 1508 Equipment 题目链接 题意：给定n装备，每个装备对应5个分，现在选出k个装备，5个位置的分为每个装备最大的分，问选出最大的分和是多少 思路：5个分，那么对于每个装备，选到最大位置其实有2^5总情况，先预处理出来，然后在这个基础上，每次去枚举集

UVA 1508 Equipment

题目链接

题意：给定n装备，每个装备对应5个分值，现在选出k个装备，5个位置的分值为每个装备最大的分值，问选出最大的分值和是多少

思路：5个分值，那么对于每个装备，选到最大值位置其实有2^5总情况，先预处理出来，然后在这个基础上，每次去枚举集合即可，最多只要枚举5个集合（因为如果k > 5的话，其实答案就是选出5个分值对应最大的5个装备，其余随便选即可)

代码：

#include <cstdio>
#include <cstring>
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 5;
int t, n, k, a[N], s[(1<<n) +="" 5];="" void="" build()="" {="" for="" (int="" i="0;" <="" (1<<5);="" i++)="" int="" sum="0;" j="0;" 5;="" j++)="" if="" (i&(1<<j))="" }="" s[i]="max(s[i]," sum);="" dfs(int="" st,="" d)="" (d="=" k)="" (st="" !="0)" return="" -inf;="" 0;="" ans="0;" i;="" -="" 1)&st)="" dfs(st^i,="" d="" 1)="" s[i]);="" ans;="" main()="" scanf("%d",="" &t);="" while="" (t--)="" scanf("%d%d",="" &n,="" &k);="" k="min(k," 5);="" memset(s,="" 0,="" sizeof(s));="" n;="" &a[j]);="" build();="" printf("%d\n",="" dfs((1<<5)="" 1,="" 0));="" }<="" script=""></n)></cstring></cstdio>