- Today
- Total
Running Deeper C/C++/Java
Circular Barn Revisited 성공
시간 제한메모리 제한제출정답맞은 사람정답 비율
| 2 초 | 512 MB | 52 | 29 | 26 | 61.905% |
문제
After the last debacle involving Farmer John's circular barn, one would think he had learned his lesson about non-traditional architecture. However, he thinks he can still make his circular barn (from the preceding problem) function properly by allowing multiple cows into each room. To recap, the barn consists of a ring of n rooms, numbered clockwise from 1…n around the perimeter of the barn (3≤n≤100). Each room has doors to its two neighboring rooms, and also a door opening to the exterior of the barn.
Farmer John wants exactly ri cows to end up in room i (1≤ri≤1,000,000). To herd the cows into the barn in an orderly fashion, he plans to unlock kexterior doors (1≤k≤7), allowing the cows to enter through only those doors. Each cow then walks clockwise through the rooms until she reaches a suitable destination. Farmer John wants to unlock the exterior doors that will cause his cows to collectively walk a minimum total amount of distance after entering the barn (they can initially line up however they like outside the k unlocked doors; this does not contribute to the total distance in question). Please determine the minimum total distance his cows will need to walk, if he chooses the best k such doors to unlock.
입력
The first line of input contains n and k. Each of the remaining n lines contain r1…rn.
출력
Please write out the minimum amount of distance the cows need to travel.
Circular Barn Revisited looks a lot like the previous problem, but is actually quite different. The N count is very low, so even an algorith of n^4 can barely make the cut. However, that is too close.
Since the barn is circular, one can make it linear, setting the start of the array as a barn. To test all cases, this can simply be done N times.
The cases then simply consist of a n*n*k dynamic, resulting in a n^3*7 dynamic solution.
Circular Barn Revisited 성공
시간 제한메모리 제한제출정답맞은 사람정답 비율
| 2 초 | 512 MB | 52 | 29 | 26 | 61.905% |
문제
After the last debacle involving Farmer John's circular barn, one would think he had learned his lesson about non-traditional architecture. However, he thinks he can still make his circular barn (from the preceding problem) function properly by allowing multiple cows into each room. To recap, the barn consists of a ring of n rooms, numbered clockwise from 1…n around the perimeter of the barn (3≤n≤100). Each room has doors to its two neighboring rooms, and also a door opening to the exterior of the barn.
Farmer John wants exactly ri cows to end up in room i (1≤ri≤1,000,000). To herd the cows into the barn in an orderly fashion, he plans to unlock kexterior doors (1≤k≤7), allowing the cows to enter through only those doors. Each cow then walks clockwise through the rooms until she reaches a suitable destination. Farmer John wants to unlock the exterior doors that will cause his cows to collectively walk a minimum total amount of distance after entering the barn (they can initially line up however they like outside the k unlocked doors; this does not contribute to the total distance in question). Please determine the minimum total distance his cows will need to walk, if he chooses the best k such doors to unlock.
입력
The first line of input contains n and k. Each of the remaining n lines contain r1…rn.
출력
Please write out the minimum amount of distance the cows need to travel.
Circular Barn Revisited looks a lot like the previous problem, but is actually quite different. The N count is very low, so even an algorith of n^4 can barely make the cut. However, that is too close.
Since the barn is circular, one can make it linear, setting the start of the array as a barn. To test all cases, this can simply be done N times.
The cases then simply consist of a n*n*k dynamic, resulting in a n^3*7 dynamic solution.