본문 바로가기

Programming Problems/Recursive

폭탄 터트려서 최대 점수 얻기

스테이트가 정리가 안되서 결국 완전탐색 선에서 귀결되는 문제가 된다고 하네. DP 솔루션이 있을까? 근데 DP가 별거냐 그냥 완.탐에 범위상한 붙인거지..


int N, v[22], r[22], dp[ 1 << 22 ];  // init dp to -1 == not done

bool Contains(int mask, int i) { return mask & (1 << i); }

bool Conflicts(int i, int j) { // j affects i
	return (abs(i-j) <= r[j] || abs(i+N-j) <= r[j] || abs(j+N-i) <= r[j]);
}
int Go(int used_mask) {
    if (dp[used_mask] != -1) // already done before?
        return dp[used_mask];
    dp[used_mask] = 0;
    for (int i = 0; i < N; i++)
        if ( ! Contains(used_mask, i) ) {
            bool ok = true;
            for (int j = 0 ; j < N ; j++)
                if (Contains(used_mask, j) && Conflicts(i,j)) {
                    ok = false;
                    break;
               } 
           if (ok)
               dp[used_mask] = max( dp[used_mask], v[i] + Go(used_mask | (1<<i)));
       }
    return dp[used_mask];
}

int main() {
	int i;
	scanf("%d", &N);
	for (i = 0 ; i < N ; i++)
		scanf("%d %d", &r[i], &v[i]);
	memset(dp, -1, sizeof dp);
	printf("%d\n", Go(0));
	return 0;
}