uva1507(狀态壓縮+dfs)

題意：

給出我們n種物品，每種物品都有五個值，分别是a、b、c、d、e，我們要在這n個物品中選出k個，使得這k個物品中的max{a}+max{b}+max{c}+max{d}+max{e}最大，輸出最大值。

思路：

n的範圍有10000，而每個人隻有五個值，我們不能從n入手，可以從這五個值入手。

五個值，我們可以用二進制進行壓縮，對于一個物品，我們用00000~11111來表示所有情況，如果某一位是1代表我們最後要取走這個物品的那個值，如10000代表我們取走a，

我們把所有物品的這32個值（00000~11111）預處理出來，然後跑dfs就可以了。

代碼：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<sstream>

using namespace std;

int n,k;
int num[1050][10];
int state_max[50];

int dfs(int state,int num)
{
	if(num==0)
		return 0;
	int ans=0;
	for(int i=state;i>0;i=(i-1)&state)
	{
//		printf("s0=%d\n",i);
		int tmp=dfs((i^state),num-1)+state_max[i];
		ans=max(ans,tmp);
	}
	return 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",&num[i][j]);
	
		memset(state_max,0,sizeof state_max);
		for(int i=0;i<n;i++)
			for(int j=0;j<=31;j++)
			{
				int tmp=0;
				for(int k=0;k<5;k++)
				{
					if((1<<k)&j)
						tmp+=num[i][k];
				}
				state_max[j]=max(state_max[j],tmp);
			}
		
		int ans=dfs(31,k);
		printf("%d\n",ans);
	}
	return 0;
}