uva331

题目大意是 只能利用左右交换完成一次排序，求一共有几种最小交换次数的方法

按照题目的意思来dfs就行了。。自己写又写烦了。。受之前一道类似的题目影响，先求出最小方法数然后用子集构造去做。最后WA而且逆序多的话就卡了

学习了别人的写法比较简单

题目：

Mapping the Swaps 

Sorting an array can be done by swapping certain pairs of adjacent entries in the array. This is the fundamental technique used in the well-known bubble sort. If we list the identities of the pairs to be swapped, in the sequence they are to be swapped, we obtain what might be called a swap map. For example, suppose we wish to sort the array A whose elements are 3, 2, and 1 in that order. If the subscripts for this array are 1, 2, and 3, sorting the array can be accomplished by swapping A2 and A3, then swapping A1 and A2, and finally swapping A2 and A3. If a pair is identified in a swap map by indicating the subscript of the first element of the pair to be swapped, then this sorting process would be characterized with the swap map 2 1 2.

It is instructive to note that there may be many ways in which swapping of adjacent array entries can be used to sort an array. The previous array, containing 3 2 1, could also be sorted by swapping A1 and A2, then swapping A2 and A3, and finally swapping A1 and A2 again. The swap map that describes this sorting sequence is 1 2 1.

For a given array, how many different swap maps exist? A little thought will show that there are an infinite number of swap maps, since sequential swapping of an arbitrary pair of elements will not change the order of the elements. Thus the swap map 1 1 1 2 1 will also leave our array elements in ascending order. But how many swap maps of minimum size will place a given array in order? That is the question you are to answer in this problem.

Input

The input data will contain an arbitrary number of test cases, followed by a single 0. Each test case will have a integer n that gives the size of an array, and will be followed by the n integer values in the array.

Output

For each test case, print a message similar to those shown in the sample output below. In no test case will n be larger than 5.

Sample Input

2 9 7
2 12 50
3 3 2 1
3 9 1 5
0

Sample Output

There are 1 swap maps for input data set 1.
There are 0 swap maps for input data set 2.
There are 2 swap maps for input data set 3.
There are 1 swap maps for input data set 4.



WA 代码：

#include <iostream>
#include <set>
#include <algorithm>
#include <cstdio>
#include <memory.h>
using namespace std;
typedef int State[10];
int arr[10];
State x;
int n;
int findmin()
{
    State tmp ;
    int ans=0;
    memcpy(tmp,arr,sizeof(tmp));
    for(int i=0;i<n-1;i++)
        {
            int pos=i,MIN=tmp[i];
            for(int j=i+1;j<n;j++)
            {
                if( tmp[j]<MIN)
                {
                    pos=j; MIN=tmp[j];
                }
            }
            if(pos!=i)
            {
                for(int m=pos;m>i;m--)
                    swap(tmp[m],tmp[m-1]);
                ans+= pos-i;
            }
        }
        return ans;
}

int B[50];
int ans=0;
void  dfs(int cur,int MIN)
{
    if(cur>MIN)
    {
//
//            for(int i=0;i<MIN;i++)
//                cout<<B[i];
//            cout<<endl;
        bool flag =false;
        int test[10];
        memcpy(test,arr,sizeof(test));
        for(int i=0;i<MIN;i++)
        {
            swap(test[B[i]],test[B[i]+1]);
        }
//        for(int i=0;i<n;i++)
//            cout<<test[i];
//        cout<<endl;
        if(MIN==0)return;
        for(int i=0;i<n;i++)
        {
            if(test[i]!=x[i])
            {
                flag= true;
                break;
            }
        }
        if(flag)
            return;
        else
        {
//            cout<<"Success: ";
//            for(int i=0;i<MIN;i++)
//                cout<<B[i];
//            cout<<endl;
            ans++;
        }
        return;
    }

    for(int i=0;i<n-1;i++)
    {
        B[cur] = i;
        dfs(cur+1,MIN);
    }
    return;
}
int main()
{

  //  freopen("in.txt","r",stdin);
    int cst=0;
    while(cin>>n && n!=0)
    {

        for(int i=0;i<n;i++)
        {
            cin>>arr[i];
        }
        memcpy(x,arr,sizeof(x));

        int MIN=0;
        sort(x,x+n);
        MIN=findmin();
       // cout<<"MIN    "<<MIN<<endl;

        for(int i=0;i<n-1;i++)
        {
            B[0] = i;
            dfs(1,MIN);
        }
        if(ans>1)
            cout<<"There are "<<ans/2<<" swap maps for input data set "<<++cst<<"."<<endl;
        else
            cout<<"There are "<<ans<<" swap maps for input data set "<<++cst<<"."<<endl;
        memset(B,0,sizeof(B));
        ans=0;
    }

    return 0;
}

AC代码：

#include <iostream>
#include <set>
#include <cstdio>
#include <algorithm>
#include <memory.h>
using namespace std;


int A[10];
int B[10];
int n;
int ans=0;
void dfs()
{
    if(memcmp(A,B,sizeof(A))==0)
    {
        ans++;
        return;
    }

    for(int i=0;i<n-1;i++)
    {
        if(B[i]>B[i+1])
        {
            swap(B[i],B[i+1]);
            dfs();
            swap(B[i],B[i+1]);
        }
    }

}
int main()
{
   // freopen("in.txt","r",stdin);
    int cst=0;
    while(cin>>n && n!=0)
    {

        for(int i=0;i<n;i++)
        {
            cin>>A[i];
        }
        memcpy(B,A,sizeof(B));

        sort(A,A+n);
        ans=0;
        if(memcmp(A,B,sizeof(A)))
        {
            dfs();
        }
        cout<<"There are "<<ans<<" swap maps for input data set "<<++cst<<"."<<endl;
    }

    return 0;
}