The traveling salesman has decided that optimally scheduling his trips on land is an intractable computational problem, 외판원은 결정 했다. 최적의 스케쥴은 컴퓨터에서 다루기 힘든 문제라는 것을. so he is moving his business to the linear world of the Danube River. 그래서 근 그의 사업을 다뉴버 강을 따라 사업을 옮기기로 . He has a very fast boat that can get him from anywhere to anywhere along the river in no time, 그는 매운 빠른 보트를 가지고 있다. 이 보트는 강을 따라 어떤 곳으로 이동할 때 시간이 걸리지 않는다. but unfortunately the boat has terrible fuel consumption. 불행히도 이 보트는 기름먹는 하마이다. It costs the salesman U dollars for every meter traveled upstream (towards the source of the river) and D dollars for every meter traveled downstream (away from the source of the river). 강을 거슬러 올라가는데 U 달러가 내려가는데 D 달러가 소요된다.
There are N trade fairs that the salesman would like to visit along the river. 강을 따라 세일즈 맨이 방문해야할 N 개의 무역 박람회가 있다. Each trade fair is held for one day only. 모든 박람회는 하루만 열린다. For each trade fair X, the traveling salesman knows its date TX, measured in the number of days since he purchased his boat. 각 무역박람회 X , 세일즈맨은 데이트 TX 를 안다. 그가 그이 보트를 산 후의 날의 수로 측정되어진... He also knows the fair’s location LX, 또한 박람회의 위치 LX 를 안다. measured as the distance in meters from the source of the river downstream to the fair, 강의 다운스트림에서 박람회까지 측정한 미터 단위 거리로.. as well as the number of dollars MX that the salesman is going to gain if he attends this trade fair. 달러 MX 도 안다. 세일즈맨이 이 박람회를 참가할 경우 버는 He has to start and end his journey at his waterfront home on the river, waterfront 에서 시작하고 끝도 여기에서 끝나야 한다. which is at location S, measured also in meters downstream from the source of the river. 위치 S 이다. 강의 소스에서 미터 다운스트림으로 측정한.. Help the traveling salesman choose which trade fairs to attend (if any) and in what order, 세일즈 맨을 도와 어떤 박람회를 참가해야 하는지 어떤 순서로 도와라. so that he may maximize his profit at the end of his travels. 여행이 끝난 후 그의 수입을 최대화 하기 위해 The traveling salesman’s total profit is defined as the sum of the dollars he gained at the fairs he attended, minus the total sum of dollars he spent traveling up and down the river. 세일즈맨의 전체 수입은 그가 참가한 박람호ㅢ의 수입에서 그가 강을 위/아래로 다니면서 소비한 금액을 뺀 금액이다.
Keep in mind that 주의 해야 한다. if trade fair A is held earlier than trade fair B, 박람회 A 가 박람회 B 보다 먼저 열렸다면 , the salesman can visit them only in this order 세일즈맨은 이 순서로만 방문할 수 있다. (i.e., he cannot visit B and then visit A). 즉 B -> A 순으로는 방문할 수 없다. However, if two fairs are held on the same date, 그러나 두개의 박람회가 같은 날에 열린다면 , the salesman can visit them both in any order. 어떤 순서로 방문하든 상관 없다. There is no limit to how many fairs the salesman can visit in a day, but naturally he can't visit the same fair twice and reap the gains twice. 하루에 얼마나 많은 박람회를 방문하던 상관이 없지만 같은 박람회를 두 번 방문할 수는 없다. He can pass through fairs he has already visited without gaining anything. 그는 이 박람회를 그냥 지나칠 수는 있다.
입력 4 5 3 100 2 80 100 20 125 130 10 75 150 5 120 110 출력 50 An optimal schedule would visit fairs 1 and 3 (the ones at locations 80 and 75). The sequence of events and their associated profits and costs would be as follows: The salesman travels 20 meters upstream at a cost of 100 dollars. Profit so far: -100 He attends fair number 1 and earns 100. Profit so far: 0 He travels 5 meters upstream at a cost of 25. Profit so far: -25 He attends fair number 3 where he earns 150. Profit so far: 125 He travels 25 meters downstream to return home at a cost of 75. Profit at the end: 50
출처: International Olympiad In Informatics 2009