글 읽기 - if문 성능에 대한 이상한 사항

yjlee270 7년 전 0

int& r = dp[cnt][S];
if (r != -1) return r; <-- 이 if문에는 통과하고

if(r>0) return r; <-- 이런 if 문에는 시간초과가 납니다. ... 어떤 문제일까요??

초기화가 혹시 잘못 되었나 초기화를 memset으로 바꾸고 전체 array에 대해서 -1로 설정해도 같습니다

이해가 안가네요.

#include <cstdio>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>


const int INFI = 987654321;
const int MXN = 16;
const int MXL = 20;
int N, P;
int cost[MXL][MXL];

int dp[MXL][(1 << MXN)];

char state[20];

using namespace std;

inline int minv(int a, int b) { return (a < b) ? a : b; }


int go(int cnt, int S) 
{
	if (cnt >= P) return 0;

	int& r = dp[cnt][S];
	if (r != -1) return r;
	r = INFI;

	for (int on= 0; on < N; on++) {
		if (S & (1<<on)) {		// on
			for (int off = 0; off < N; off++) {
				if (!(S & (1<<off)) ) {		// off
					r = minv(r, go(cnt + 1, S | (1 << off)) + cost[on][off]);
				}
			}
		}
	}
	return r;
}

int main()
{
	int i, j;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			scanf("%d", &cost[i][j]);
		}
	}
#if 1
	memset(dp, -1, sizeof dp);
#else
	for (i = 0; i < N; i++) {
		for (j = 0; j < (1 << N); j++) {
			dp[i][j] = -1;
		}
	}
#endif
	scanf("%s", state);

	int S = 0, cnt = 0;
	for (int i = 0; i < N; i++) {
		if(state[i] == 'Y'){
			S |= (1 << i);
			cnt++;
		}
	}

	scanf("%d", &P);

	int res = go(cnt, S);
	printf("%d\n", res);
    return 0;
}

yukariko 7년 전 1

간단합니다.

r = 0이 되는 경우도 걸러야하는데 위 코드는 그러지 못하기 때문입니다.

yjlee270 7년 전 0

착각을 했네요

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

문제

문제

출처

ICPC

if문 성능에 대한 이상한 사항

yjlee270 7년 전 0

yukariko 7년 전 1

yjlee270 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말