Given a list of noises generated by all pairs of animals, determine the least sum of noise that can be generated.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Story

The animals have been making too much noise, and guests are complaining. Some animals antagonize nearby animals and cause them to emit screams of rage or cries of annoyance. You have experimented with different animals next to each other, and you feel that you now have enough information to move forward with your plans.

 

The animals will be in a line of exhibits. Each animal will be in its own exhibit, and there are an equal number of animals as exhibits. You have found that animals only antagonize the animals in exhibits within 2 exhibits of them. Animals that are antagonized will generate a specific level of noise. The total noise of the park is the sum of all the levels of noises generated.

 

To alleviate some stress from the animals and pain from the guests ear’s you will attempt to find some animal ordering that is a few decibels lower.

 

Problem

Given a list of noises generated by all pairs of animals, determine the least sum of noise that can be generated.

 

Input

Input will begin with a line containing 1 integer, n (1 ≤ n ≤ 11), representing the number of animal exhibits. The following n lines will each contain n space separated non-negative integers, representing the noises generated by animal pairs. The i-th value on the j-th line represents the noise level generated by animal j when antagonized by animal i. Each of the given individual noise levels generated will be at most 1,000,000. The i-th value of the i-th line will always be 0. Animals don’t generate noise from themselves.

 

 

Attachments:

Expert's Answer

521 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of