I. 越狱

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 19 Accepted Submission(s) : 10

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

有一座监狱有N个房间，从1编号至N，房间呈线性排列，i和i+1号房间相邻。现在我们需要你来帮助我们救出一些犯人。
已知最初的时候每个房间有且仅有一个犯人，其中某些房间关着你需要救出的犯人。你只需要假扮成狱警把钥匙偷偷递给我们要救出的犯人，他就能逃出。但现在关键的问题是，
当一个房间里的犯人不见了之后，相邻房间的犯人会立即发现，并扩散给相邻房间的人，一直扩散直到房间的尽头，即1号或N号房间，或某个空房间。并且这些犯人一旦知道有人逃离之后，如果不进行贿赂，就会大吵大闹，导致救人失败。
幸运的是，对于每个犯人，只需要一个金币就可以贿赂。
我们打算每天救出一个犯人，需要注意的是，贿赂的效果只能维持一天。现在需要你算出最少需要多少金币才能救出我们要救的犯人。

Input

第一行一个整数Cases，表示有Cases组测试数据
第二行两个整数N,P，表示有N个房间，我们需要救出P个犯人。
第三行P个整数，表示我们要救出的犯人所在房间编号，以升序给出。
其中 1<=Cases<=100
   1<=N<=10000
   1<=P<=100
   P<=N

Output

Case #X: Y
其中X表示第几组测试数据，从1开始编号，Y表示最少需要的金币数。
注意#号前和:号后均有一个空格

提示：
对于第二组数据，如果先救14号房间的犯人，再6号，再3号的话，需要19+12+4=35金币，
但如果你先救6号犯人，再14号，再3号的话，再6号的话，需要19+13+4=36金币
而如果6号，3号，再14号，需要，19+4+13=36金币，所以最少是35金币

Sample Input

Sample Output

Case #1: 7
Case #2: 35

Author

twinkle

Source

developing schools contest 5

Statistic | Submit | Back