[HDU] 2610 Sequence one 非地图求解类的广搜，注意空间复杂度

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2610

方法：状态收索树中的每一个节点包含如下信息，

　　A.当前数组中的个数。

　　B.当前数组中最后一个数在原数组中的位置。

　　C.一个指向 当前数组的指针在指针数组中为值得编号。

由于每一个状态节点中的数组长度不定，所有都用int* 来动态为其分配空间。这样在进出队列的时候还可以减少副本开销。

每一个状态节点在广搜探寻下一个节点的时候，先从自己当前数组最后一个数在源数组中的位置后第一个位置开始，以下标的顺序不重复地找寻大于等于当前数组最后一个数的数x 以及其下标i，然后，然后给新节点的数组中数字个数赋为当前节点的数组的个数加一， 把当前节点中数字全部顺序拷贝给新节点，然后把找到的x拷贝到新节点的数组的最后一个元素上，并设置i为最后一个元素的位置，最后进入队列 以此类推。

初始化的时候，先将原数组的每一个数不重复地拿来建立状态节点，入队列，再出队列输出，再用上述方法继续压入新探寻到的状态节点入队。。。

再探寻新节点的时候，要判断当前进入队列的状态数目有没有超过要求输出的序列个数，超出了就不需要再找了。

这里输出要求的顺序就只是依据长度和下标，首先看长度，整个算法就是用“短长度”的状态去探寻的“长长度”的状态，所以，长度肯定满足，而再下标，由于“短长度”的状态去探寻的“长长度”过程中都是从短长度的最后一个位子后的第一个数字按下标顺序一个一个找的，所以也满足，这也是为什么当进入队列的状态数目超过要求输出的序列个数时就不找了。

除此之外，由于数组中的数字会很大，如果直接以下标去访问标志其是否访问的信息，就会需要非常巨大但使用效率不高的存储空间。如果用map进行压缩。

感想：据说用深搜更快；数组拷贝占用大量的时间空间开销，以后要优化，当前先ac了再说。

代码：

#include <iostream>
#include <queue>
#include <map>
using namespace std;
int n,p;
int numbers[1001];
bool visisted[1001];
int* arrays[20001];
struct Nums
{
    int count;
    int numbersNo;
    int end;
};
int t_n;
void  BFSearch(map <int,int>::iterator iter,map <int,int> mp)
{
     queue<Nums> q;
     int curr=0;
     int i =0;
     for(i=0;i<n;i++)
     {
         iter = mp.find(numbers[i]);
         if(!visisted[ iter->second])
         {
            Nums nums;
            nums.count=1;
            nums.end=i;
            nums.numbersNo=i;
            arrays[    nums.numbersNo] =new int[1];
            arrays[    nums.numbersNo][0] = numbers[i];
            visisted[iter->second] = true;
            q.push(nums);
         }
     }
     curr = i;
     int count =0;
     while(!q.empty() && count<p)
     {
         memset(visisted,false,sizeof(visisted));
         Nums t_nums = q.front();
         q.pop();
          count++;
         //printf("%d----------",count);
         //if(count == 2539)
         //{
            // int ixz=0;
         //}
         for(int j=0;j<t_nums.count-1;j++)
         {
             printf("%d ",arrays[t_nums.numbersNo][j]);
         }
         printf("%d\n",arrays[t_nums.numbersNo][t_nums.count-1]);
              
         Nums n_nums;
         
         for(int j=t_nums.end+1;j<n;j++)
         {
             
             iter = mp.find(numbers[j]);
             if(numbers[j]>=numbers[t_nums.end] && !visisted[iter->second] && curr<=10001)
             {
                 visisted[iter->second] = true;
                 n_nums.count = t_nums.count+1;
                 n_nums.end = j;
                 n_nums.numbersNo = curr;
                 arrays[n_nums.numbersNo] = new int[n_nums.count];
                 int x=0;
                 for(x=0;x<t_nums.count;x++)
                    arrays[n_nums.numbersNo][x] = arrays[t_nums.numbersNo][x];
                arrays[n_nums.numbersNo][x]=numbers[j];
                q.push(n_nums);
                curr++;
             }
              //if(t_n!=n)
                 //{
                    // n=t_n;
                 //}
         }
         delete[]  arrays[t_nums.numbersNo];
     }
}
void map_insert(map < int, int > *mapStudent, int o, int x) 
{ 
    mapStudent->insert(map < int, int >::value_type(o, x)); 
} 

void main()
{
    while(scanf("%d %d",&n,&p)!=EOF)
    {
        map <int,int>::iterator iter;
        map <int,int> mp;
        memset(numbers,0,sizeof(numbers));
        memset(visisted,false,sizeof(visisted));
        int k =0;
        t_n=n;
        for(int i =0;i<n;i++)
        {
            scanf("%d",&numbers[i]);
            iter = mp.find(numbers[i]);
            if(iter ==mp.end())
            {
                map_insert(&mp,numbers[i],k);
                k++;
            }
        }
         BFSearch(iter,mp);
        printf("\n");
    }
}