글 읽기 - bitmask dp 질문입니다.

lyzqm 6년 전 1

75%정도에서 틀리는데 어디서 잘못했을까요?

dp[info][from] : 현재 info에 bitmask로 켜진 발전소가 저장, from으로 부터 꺼진 발전소를 킬때 최소 비용

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 987654321
int N, P;
int dp[1 << 16][17];
int cost[17][17];
char on[17];
int getInfoCnt(int info){
	int cnt = 0;
	for (int n = 0; n < N; n++){
		if ((info & (1 << n)) > 0)
			cnt++;
	}
	return cnt;
}
int solve(int info, int from){		//from으로 부터 다음 발전소를 재시작
	if (getInfoCnt(info) >= P) return 0;		//base : 켜진 발전소가 P개 이상일 경우

	int &ret = dp[info][from];
	if (ret != -1) return ret;
	ret = INF;
	for (int n = 0; n < N; n++){			// n : from->n 으로 재시작될 발전소
		if ((info & (1 << n)) == 0){		// n : 꺼져있는것중에서 선택
			int ninfo = info | (1 << n);
			for (int next = 0; next < N; next++){		// next : 다음 from 선택
				if ((ninfo & (1 << next)) > 0)			// n포함 켜진 발전소에서 선택
					ret = min(ret, solve(ninfo, next) + cost[from][n]);
			}
		}
	}
	return ret;
}
int main(){
	memset(dp, -1, sizeof(dp));
	scanf("%d", &N);
	for (int n = 0; n < N; n++)
		for (int m = 0; m < N; m++)
			scanf("%d", &cost[n][m]);
	scanf("%s", on);
	scanf("%d", &P);

	int ans = INF, info = 0;
	for (int n = 0; n < N; n++)
		if (on[n] == 'Y')
			info |= (1 << n);		//처음 info 저장

	for (int n = 0; n < N; n++)
		if (on[n] == 'Y')
			ans = min(ans, solve(info, n));		
	printf("%d\n", ans == INF ? -1 : ans);
	return 0;
}

lyzqm 6년 전 1

켜진발전소가 없고 P가 0일때 값이 잘못나왔네요 ㅎㅎ

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

문제

문제

출처

ICPC

bitmask dp 질문입니다.

lyzqm 6년 전 1

lyzqm 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말