글 읽기 - 발전소 질문 드립니다! ㅠ.

goodksj 7년 전 0

문제에서 불가능한 경우에 -1을 출력하라고 했는데

-1을 출력하는 경우가 어떤 경우가 있죠?

휴.. 그리고 제가 짠 dp가 다음과 같은데

어디서 틀렸는지 모르겠습니다 고수님들 도와주세요!

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int INF = 999999999;
int N;
int price[20][20];
int cache[20][20];
int P;
string state;

int repair(int broken, int station_num);
int main(){
	freopen("input.txt","r",stdin);
	cin>>N;
	memset(cache, -1, sizeof(cache));
	for(int i = 0 ; i < N ; i++){
		for(int j = 0; j < N; j++){
			cin>>price[i][j];
		}
	}
	int broken = 0;
	cin>>state; cin>>P;
	for(int i = 0 ; i< state.size();i++){
		if(state[i] == 'N')
			broken++;
	}

	cout<<repair(broken, 0)<<endl;

	return 0;
}
int repair(int broken, int station_num){ 

	int& ret = cache[broken][station_num];

	if(ret != -1) return ret;
	
	ret = INF;

	if(state[station_num] == 'Y'){
		for(int next = station_num + 1; next < N; next++){
			ret = min(ret, repair(broken, next));
		}
	}
	else{
		int min_price = INF;
		for(int i = 0; i < N; i++){
			if(i != station_num)
				min_price = min(min_price, price[i][station_num]);
		}
		
		for(int next = station_num+1; next < N; next++){
			ret = min(ret, repair(broken-1, next) + min_price);
		}
		if(N - P >= broken-1) ret = min(ret,min_price);
	}

	return ret;
}

zlzmsrhak 7년 전 0

1. -1인 경우는 없습니다.

2. 문제가 모든 발전소를 켜는 것이 아니기 때문에 49-51번째 줄에서 구하는 min_price가 valid한 값이 아닐 수 있습니다.

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

문제

문제

출처

ICPC

발전소 질문 드립니다! ㅠ.

goodksj 7년 전 0

zlzmsrhak 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말