当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3003:Spiderman’s workout

Special Judge 特殊评判
题目描述
Staying fit is important for every super hero, and Spiderman is no exception. Every day he undertakes a climbing exercise in which he climbs a certain distance, rests for a minute, then climbs again, rests again, and so on. The exercise is described by a sequence of distances d1, d2, . . . , dm telling how many meters he is to climb before the first first break, before the second break, and so on. Froman exercise perspective it does not really matter if he climbs up or down at the i:th climbing stage, but it is practical to sometimes climb up and sometimes climb down so that he both starts and finishes at street level. Obviously, he can never be below street level. Also, he would like to use as low a building as possible (he does not like to admit it, but he is actually afraid of heights). The building must be at least 2 meters higher than the highest point his feet reach during the workout.

He wants your help in determining when he should go up and when he should go down. The answer must be legal: it must start and end at street level (0 meters above ground) and it may never go below street level. Among the legal solutions he wants one that minimizes the required building height. When looking for a solution, you may not reorder the distances.

If the distances are 20 20 20 20 he can either climb up, up, down, down or up, down, up, down. Both are legal, but the second one is better (in fact optimal) because it only requires a building of height 22, whereas the first one requires a building of height 42. If the distances are 3 2 5 3 1 2, an optimal legal solution is to go up, up, down, up, down, down. Note that for some distance sequences there is no legal solution at all (e.g., for 3 4 2 1 6 4 5).
输入解释
The first line of the input contains an integer N giving the number of test scenarios. The following 2N lines specify the test scenarios, two lines per scenario: the first line gives a positive integer M ≤ 40 which is the number of distances, and the following line contains the M positive integer distances. For any scenario, the total distance climbed (the sum of the distances in that scenario) is at most 1000.
输出解释
For each input scenario a single line should be output. This line should either be the string "IMPOSSIBLE" if no legal solution exists, or it should be a string of length M containing only the characters "U" and "D", where the i:th character indicates if Spiderman should climb up or down at the i:th stage. If there are several different legal and optimal solutions, output one of them (it does not matter which one as long as it is optimal).
输入样例
3
4
20 20 20 20
6
3 2 5 3 1 2
7
3 4 2 1 6 4 5
输出样例
UDUD
UUDUDD
IMPOSSIBLE

该题目是Virtual Judge题目,来自 北京大学POJ

源链接: POJ-3003

最后修改于 2020-10-29T06:49:35+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 65536