# hihoCoder 1233 : Boxes（盒子）

### Description - 题目描述

There is a strange storehouse in PKU. In this storehouse there are n slots for boxes, forming a line. In each slot you can pile up any amount of boxes. The limitation is that you can only pile a smaller one above a bigger one, in order to keep balance. The slots are numbered from 1 to n. The leftmost one is slot 1.

At first there is exactly one box in each slot. The volume of the box in slot i is vi. As a virgo, you decide to sort these boxes by moving some of them. In each move you can choose a slot and move the top box in this slot to an adjacent slot (of course you can only put it on the top). You should ensure that the limitation mentioned above is still satisfied after this move. After the sort operation, there should be exactly one box in each slot, and for each pair of adjacent slots, the box in the left one should be smaller than the box in the right one.

Your task is to calculate the minimum number of moves you need to sort the boxes.

```PKU里有个奇怪的仓库。仓库里有n个连成一线的盒子槽。每个槽上可以叠堆人员数量的盒子。为了保持平衡，唯一的限制是：只能把小盒子放在大盒子上面。槽的编号为从1到n。最左边的槽为1。

CN

### Input - 输入

In the first line there’s an integer T(T≤6000), indicating the number of test cases. The following 2T lines describe the test cases.

In each test case, the first line contains an integer n, indicating the number of slots. The second line contains n integers v1,v2…vn, indicating the volume of the boxes. It is guaranteed that all vi in a test case are different.

```第一行有一个整数T，表示测试用例的数量。随后有2T行的测试用例。

CN

### Output - 输出

For each test case, print a line containing one integer indicating the answer. If it’s impossible to sort the boxes, print -1.

`对于每组测试用例，输出一行整数答案。如果无法完成盒子排序，输出-1。`

CN

Sample Input - 样例输入

```4
3
2 1 3
2
7 8
2
10000 1000
3
97 96 95
```

Sample Output - 样例输出

```4
0
-1
20
```

开始时脑袋一抽冒了个2^（8*8）的状态表示，看到2^21后恍然大悟。 写完时没注意T，弄了个在线查询超时了……默默地改成打表

压缩状态：

[1--] [2--] [3--] [4--] [5--] [6--] [7--]

最多7个数，把数字离散化成位置。

用3位二进制标记第i小的数存放的位置，[0, 6]或[1, 7]的方式都差不多。 状态数2^（3*7）。

（但是想了想为什么不把3位全用上，估计是因为2^（3*8）……）

后面就是BFS打表，枚举所有情况。

``` 1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <queue>
5 int n, ed, bit[8] = { 1 }, map[10005];
6 unsigned int opt[2 << 21 | 1], data[8];
7 std::queue<int> q;
8
9 int red(){
10     int now, tmp[8], i;
11     scanf("%d", &n);
12     for (i = 0; i < n; ++i) scanf("%d", data + i);
13     memcpy(tmp, data, sizeof data);
14     std::sort(tmp, tmp + n);
15     for (i = 0; i < n; ++i) map[tmp[i]] = i;
16     for (i = now = 0; i < n; ++i) now ^= bit[map[data[i]]] * (i + 1);
17     return now;
18 }
19
20 void setData(int d){
21     int i, j;
22     memset(data, -1, sizeof data);
23     for (i = 1; i <= n; ++i, d >>= 3){
24         if (~data[j = (d & 7) - 1]) continue;
25         data[j] = i;
26     }
27 }
28 void BFS(){
29     int now, nxt, i;
30     while (!q.empty()){
31         setData(now = q.front()); q.pop();
32         for (i = 0; i < n; ++i){
33             if (data[i] == -1) continue;
34             if (i < n - 1){
35                 if (data[i] < data[i + 1]){
36                     nxt = now + bit[data[i] - 1];
37                     if (opt[now] + 1 < opt[nxt]) opt[nxt] = opt[now] + 1, q.push(nxt);
38                 }
39             }
40             if (i > 0){
41                 if (data[i] < data[i - 1]){
42                     nxt = now - bit[data[i] - 1];
43                     if (opt[now] + 1 < opt[nxt]) opt[nxt] = opt[now] + 1, q.push(nxt);
44                 }
45             }
46         }
47     }
48 }
49 void rdy(){
50     memset(opt, -1, sizeof opt);
51     int now, i;
52     for (i = 1; i < 8; ++i) bit[i] = bit[i - 1] << 3;
53     for (i = now = 0; i < 7; n = ++i, BFS()){
54         q.push(now += bit[i] * (i + 1)); opt[now] = 0;
55     }
56 }
57
58 int main(){
59     rdy();
60     int t;
61     for (scanf("%d", &t); t--; printf("%d\n", opt[red()]));
62     return 0;
63 }```

## ACM学习历程—Hihocoder 1233 Boxes(bfs)（2015北京网赛）

hihoCoder挑战赛12 时间限制:1000ms 单点时限:1000ms 内存限制:256MB   描述 There is a strange storehouse in PKU. In this storehouse there are n slots for boxes, forming a line. In each slot you can pile up any amount of boxes. The limitation is that you can only pile a

## HDU 5810 Balls and Boxes（盒子与球）

HDU 5810 Balls and Boxes(盒子与球) Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Description 题目描述 Mr. Chopsticks is interested in random phenomena, and he conducts an experiment to study randomness. In the experiment

## [Swift]LeetCode546. 移除盒子 | Remove Boxes

Given several boxes with different colors represented by different positive numbers. You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (composed of k boxes

## [LeetCode] Remove Boxes 移除盒子

Given several boxes with different colors represented by different positive numbers. You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (composed of k boxes

## Uva12657 (Boxes in a Line)移动盒子

UVA 12657 Boxes in a Line You have n boxes in a line on the table numbered 1 . . . n from left to right. Your task is to simulate 4kinds of commands:• 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y )• 2 X Y : move box

## UVa 12657 Boxes in a Line(应用双链表)

Boxes in a Line You have n boxes in a line on the table numbered 1 . . . n from left to right. Your task is to simulate 4 kinds of commands: ? 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y ) ? 2 X Y : move box X to th