글 읽기 - 제발 ㅜㅜ 알려주십시요

seonh4996 5년 전 0

너무너무 답답합니다.

반례라고 하는 것들은 다 찾아보고 넣어봤는데도 답이 다르지 않아 답답하네요..

일단 기본적으로 재귀로 풀었으며 메모이제이션을 이용했습니다.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int Time[1001];
int rule[1001][1001]; // 1이면 
int cache[1001];
int rule_cnt;
int building;

int What_Time(int Win_building){
	
	int &ret=cache[Win_building];
	if(ret!=-1){return ret;}
	
	vector<int> need_building;
	
	for(int i=1; i<=building; i++){  // Win_building번호 건물을 짓기위한 번호를 찾음.
		if(rule[i][Win_building]==1){
			need_building.push_back(i);
		}
	}
	if(need_building.empty()){        // 필요한 건물이 없을시 이 건물은 기초건물.
		ret= Time[Win_building];
		
		return ret;
	}
	
	ret=-1;
	while(!need_building.empty()){ // 벡터에 들어간 건물중에 가장 오래 걸리는 건물의 시간을 찾음
		
		ret=max(ret,What_Time(need_building.back())); 
		
		need_building.pop_back();
	}
	
	return ret+Time[Win_building];
	
	
}


int main(){
	int T;
	cin >> T;

	for(int i=0; i<T; i++){
		
		fill_n(cache,1001,-1);
		for(int i=0; i<1001; i++){
		fill_n(rule[i],1001,-1);
	}
		int building_for_win;
		cin >> building >> rule_cnt;
		
		for(int j=1; j<=building; j++){
			cin >> Time[j];
		}
		
		for(int j=0; j<rule_cnt; j++){
			int a,b;
			cin >> a>> b;
			rule[a][b]=1;
			
		}
		
	
		cin >> building_for_win;
		
		cout << What_Time(building_for_win)<<endl;
		
		
	}
}

sgchoi5 5년 전 0

문제 번호를 넣어주셔야 합니다.

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

문제

문제

출처

ICPC

제발 ㅜㅜ 알려주십시요

seonh4996 5년 전 0

sgchoi5 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말