mic1021   2년 전

이 문제를 dp로 접근했습니다.

dp[i][c] = 현재 섭취한 칼로리가 c인 i번째 생물에 쌓이는 중금속량의 최솟값

for(i번째 생물의 먹이가 되는 생물들){
       dp[i][c]= min(dp[i][c-E[j]] + dp[j][C[j]] , dp[i][c-E[k]] + dp[k][C[k]]) .....
}

위 점화식을 가지고 풀어봤는데 63퍼에서 틀렸다고 나오니까 반례가 있다는 건데..

'먹이를 먹을 때는 필요한 칼로리를 섭취하면서도 축적되는 중금속은 가장 적어지도록 먹이를 먹는다.' 라는 조건을 보면 제 접근방식이 맞다고 생각합니다..

혹시 반례가 있을런지요?

mic1021   2년 전

한줄 추가하니까 맞았습니다 뜨네요 ㅂㄷㅂㄷ

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