hihoCoder 1233 Boxes(状態圧縮+bfs)-ACM-ICPC国際大学生プログラム設計コンテスト北京試合区(2015)ネット試合
タイトル7:Boxes
時間制限:
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 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.
入力
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.
Please note that n<8,0≤vi≤104
しゅつりょく
For each test case, print a line containing one integer indicating the answer. If it’s impossible to sort the boxes, print -1.
サンプル入力
サンプル出力
/*********************************************************************/
标题:n個のカードスロットがあり、体積の異なるn個の空き箱が置いてあり、毎回空き箱を隣接カードスロットに移動することができますが、前提は隣接カードスロットがすでに空き箱があれば、移動する空き箱の体積は既存の空き箱より小さくなければなりません.左から右に移動するには、どのくらいのステップで各カードスロットの空き箱の体積を増加させることができますか.
現用①は1番カードスロット、②は2番カードスロット、順次類推…
サンプル1の移動方法:1->③,2->②,1->②,1->①
サンプル3の移動方法:95->2,95->①, 96->3,95->2,95->3,97->2,95->2,95->1,96->2,95->2,95->2,95->3,96->1,95->2,95->1,97->3,95->2,95->3,96->2,95->2,95->1
解題構想:状態圧縮、状態は各箱の位置を表し、各箱の位置は3桁のバイナリで表され、合計の状態は2^21である.毎回箱は左に置くか右に置くしかないので、終了した位置から検索を開始し、bfsは目標状態からすべての状態までに必要な最小ステップ数を前処理する.そして,質問O(1)ごとに回答すればよい.
菜鳥成長記
時間制限:
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 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.
入力
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.
Please note that n<8,0≤vi≤104
しゅつりょく
For each test case, print a line containing one integer indicating the answer. If it’s impossible to sort the boxes, print -1.
サンプル入力
4
3
2 1 3
2
7 8
2
10000 1000
3
97 96 95サンプル出力
4
0
-1
20/*********************************************************************/
标题:n個のカードスロットがあり、体積の異なるn個の空き箱が置いてあり、毎回空き箱を隣接カードスロットに移動することができますが、前提は隣接カードスロットがすでに空き箱があれば、移動する空き箱の体積は既存の空き箱より小さくなければなりません.左から右に移動するには、どのくらいのステップで各カードスロットの空き箱の体積を増加させることができますか.
現用①は1番カードスロット、②は2番カードスロット、順次類推…
サンプル1の移動方法:1->③,2->②,1->②,1->①
サンプル3の移動方法:95->2,95->①, 96->3,95->2,95->3,97->2,95->2,95->1,96->2,95->2,95->2,95->3,96->1,95->2,95->1,97->3,95->2,95->3,96->2,95->2,95->1
解題構想:状態圧縮、状態は各箱の位置を表し、各箱の位置は3桁のバイナリで表され、合計の状態は2^21である.毎回箱は左に置くか右に置くしかないので、終了した位置から検索を開始し、bfsは目標状態からすべての状態までに必要な最小ステップ数を前処理する.そして,質問O(1)ごとに回答すればよい.
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define eps 1e-6
#define LL long long
#define pii pair<int, int>
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int MAXN = 5000000;
int n;
int a[10], b[10];
int vis[MAXN];
bool fuck[10];
void bfs(int n) {
queue<int> q;
int tmp = 0;
for(int i = 0; i < n; i++) {
tmp += (i+1) * (1 << (3*i));
}// n=7 ，tem = 7 * 3^6 + 6 *3^5 + 5 * 3^4 + 4 * 3^3 + 3 * 3^2 + 2 * 3^1 + 1 * 3^0
q.push(tmp);
vis[tmp] = 0;
while(!q.empty()) {
int s = q.front(); q.pop();
memset(fuck, 0, sizeof(fuck));
for(int i = 0; i < n; i++) { //i+1
int pos = (s >> (3*i)) % 8;// i+1
if(fuck[pos]) continue;//
fuck[pos] = 1;
if(pos>1 && !fuck[pos-1]) {
int t = s - (1<<(3*i));//
if(vis[t]==-1) {
q.push(t);
vis[t] = vis[s] + 1;
}
}
if(pos<n && !fuck[pos+1]) {
int t = s + (1<<(3*i));//
if(vis[t]==-1) {
q.push(t);
vis[t] = vis[s] + 1;
}
}
}
}
}
int main() {
//freopen("input.txt", "r", stdin);
int T; cin >> T;
memset(vis, -1, sizeof(vis));
for(int i = 1; i <= 7; i++) bfs(i);
while(T--) {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
sort(b+1, b+n+1);
for(int i = 1; i <= n; i++) a[i] = lower_bound(b+1, b+n+1, a[i]) - b - 1;// ， ， 1~n
int s = 0;
for(int i = 1; i <= n; i++) {
s += i*(1<<(3*a[i]));//
}
printf("%d
", vis[s]);
}
return 0;
}菜鳥成長記