uva 1507 (상태 압축 + dfs)

1518 단어 #수색 하 다.uva 코드
제목:
우리 에 게 n 가지 아 이 템 을 주 십시오. 모든 아 이 템 은 5 개의 값 이 있 습 니 다. 각각 a, b, c, d, e 입 니 다. 우 리 는 이 n 개의 아 이 템 중에서 k 개 를 선택 하여 이 k 개의 아 이 템 중의 max {a} + max {b} + max {c} + max {d} + max {e} 가 가장 크 고 출력 최대 치 입 니 다.
생각:
n 의 범 위 는 10000 이 고 모든 사람 은 5 개의 가치 만 있 습 니 다. 우 리 는 n 부터 시작 할 수 없고 이 5 개의 가치 부터 시작 할 수 있 습 니 다.
다섯 개의 값, 우 리 는 2 진법 으로 압축 할 수 있 습 니 다. 한 물건 에 대해 우 리 는 00000 ~ 11111 로 모든 상황 을 표시 합 니 다. 만약 에 한 사람 이 1 이 라면 우리 가 마지막 으로 이 물건 의 그 값 을 가 져 가 야 합 니 다. 예 를 들 어 10000 은 우리 가 a 를 가 져 가 는 것 을 대표 합 니 다.
우 리 는 모든 물품 의 이 32 개 값 (00000 ~ 1111) 을 미리 처리 한 후에 dfs 를 뛰 면 된다.
코드:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

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
",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
조합 색인 을 만 들 때 색인 열 순서 선택
HDU 3639 강 연통 축 점 최적화

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage