给定n个不同的数，问这n个数可以组成多少个不同的序列且序列中相邻的元素之差大于一。
一开始我用递归进行全排列，然后逐个比较。后来看到最多有25个数，就知道肯定超时了（时间复杂度已经达到O（n！）了）。不知各位大牛有何建议？这肯定是有简便方法的，不过我就是没想出来。。。
附上我超时的代码：
#include<iostream>
using namespace std;
int fabs(int n)
{
    if(n<0)
        return -n;
    else
        return n;
}
int counter=0;
void Swap(int& a,int& b)
{
    int temp=a;
    a=b;
    b=temp;
}
void pai(int a[],int n,int k,int end)
{
    int flag=1;
    if(k==end)
    {
        //cout<<"yes.\n";
        /*for(int i=0;i<n-1;i++)
        {
            if((a[i]-a[i+1]==1)||(a[i]-a[i+1]==-1))
                return;
        }*/
        counter++;
        return;
        /*for(int i=0;i<n;i++)
            cout<<a[i]<<" ";
        cout<<endl;*/
    }
    for(int i=k;i<n;i++)
    {
        Swap(a[k],a[i]);
        if(fabs(a[k]-a[k+1])>1)
        {
            if(k>=1)
            {
                if(fabs(a[k]-a[k-1])>1)
                    pai(a,n,k+1,end);
            }
            else
                pai(a,n,k+1,end);
        }
        
        //pai(a,n,k+1,end);
        Swap(a[k],a[i]);
    }
}

int main()
{
    int T,num;
    int a[26];
    cin>>T;
    while(T--)
    {
        counter=0;
        cin>>num;
        for(int i=0;i<num;i++)
            cin>>a[i];
        pai(a,num,0,num-1);
        cout<<counter<<endl;
        
    }
    return 0;
}

[ 本帖最后由 mahuaguan 于 2012-5-3 20:50 编辑 ]

你可以把你超时的那组data贴上来吗

那是系统测试的，它也没有给数据给我，只说超时。。。。

系统地址？

因为感觉这题和图的遍历是等价的，应该是细节上的优化

我觉得应该不是遍历的。应为有25个数，25！是一个20+位的数，遍历肯定超时的，BTW，我只有一秒。。。

不知道大家有没有什么想法？

真的没有想法吗。。。

同意czz    以后再出这题目把系统的地址给发下

http://soj.me/contest_password.php?cid=598
密码是accept

求解啊啊啊 啊啊 啊啊啊啊啊啊