글 읽기 - 예제는 다맞는데.. 알려주십시요

seonh4996 2년 전 0

재귀랑 Dp이용해서 풀었는데, 기존 게시판에있는 반례넣어도 다 맞습니다 ㅜ

#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++){
		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();
	}
	ret=ret+Time[Win_building];
	return ret;
	
	
}


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)<<'\n';
		
		
	}
}

djm03178 2년 전 0

말씀대로입니다. 이 코드 그대로 제출하면 맞습니다.

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

문제

문제

출처

ICPC

예제는 다맞는데.. 알려주십시요

seonh4996 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말