글 읽기 - DP로 풀어보고싶은데 풀이의 힌트같은것좀 알 수 있을까요 ㅜ?

isvara 4년 전 0

bitmask dp.. 어떤식으로 정의하고 풀어야할지 감이 전혀 안잡히는데 bitmaks dp로 푸신분 혹시 조금만 힌트라도 알려주실 수 있을까요..?

djm03178 4년 전 1

dp[i][x]를

i-1번째 행에 사람이 앉아있는 상태를 0과 1로 표현한 값이 x일 때, i번째 행부터 마지막 행까지 앉을 수 있는 사람의 최대 수

로 정의해 보세요.

isvara 4년 전 0

조언대로 우선 짜봤는데, 제가 비트마스크를 처음 써봐서 그런지 에러가 많이 나옵니다..

특히 solve함수안에 for문이 반복을 하지가 않네요..

코드설명을 덧붙히면 전달받은 state로 다음 행에 둘 수 없는 위치 정보를 주기위해서 cunning변수를 두고 현재 state에서 맨 왼쪽 비트를 제거하고 왼쪽으로 한칸 땡긴 집합과

state에서 오른쪽으로 한칸 땡긴 집합을 합집합해서

101010으로 두었다고 치면

010101로 다음값에 주려고 계산을 했습니다.

그 이후에 cunning과 이전에 계산해두었던 broken으로 부서진 위치 까지 만들 수 있는 집합에서 제외시키고 재귀를 호출 했는데

혹시 잘못된 지점 있으면 따끔하게 부탁드립니다. ㅜ..

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;

int N, M;
char map[11][11];
int cache[10][1<<10];//현재 row의 state상태에서 끝 행까지 둘수있는 학생 수 중 최대값
int broken[11];//=>각 행에서 부서진 위치들을 비트마스크로 미리 계산

int bitcount(int n)
{
	if (n == 0)
		return 0;
	return n % 2 + bitcount(n / 2);
} 
int solve(int rows, int state)
{	
	if (rows == N-1)
		return 0;

	int & ref = cache[rows][state];
	if (ref != -1)
		return ref;
	
	//다음 행의 컨닝가능한 위치들
	int cunning = (((state &= ~(1 << M)) << 1) | (state >> 1));
	
	for (int bit= (1 << M); bit; bit=((bit - 1)&(1 << M)))
	{
		//부서졌거나 커닝가능한 위치는 제외
		if ((cunning & bit) || (broken[rows]&bit))  
			continue;
		ref = max(ref, bitcount(bit) + solve(rows + 1, bit));
	}
	return ref;
}
int main()
{
	int C;
	cin >> C;
	while (C--)
	{
		memset(cache, -1, sizeof(cache));
		int res = 0;

		cin >> N >> M;

		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
			{
				cin >> map[i][j];
				if (map[i][j] == 'x')//부서진부분 집합에 추가
					broken[i] |= (1 << j);
			}
		solve(0, 0);
		for (int bit = (1 << M); bit; bit=((bit - 1)&(1<<M)))
			res = max(res, cache[N - 1][bit]);
		
		cout << res << endl;
	}
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

DP로 풀어보고싶은데 풀이의 힌트같은것좀 알 수 있을까요 ㅜ?

isvara 4년 전 0

djm03178 4년 전 1

isvara 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말