hdu 2611 Sequence two(深搜)

港控/mmm° 2022-04-10 08:22 169阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td> <h1>Sequence two</h1> </td> 
  </tr> 
  <tr> 
   <td>Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)</td> 
  </tr> 
  <tr> 
   <td>Total Submission(s): 98 Accepted Submission(s): 46</td> 
  </tr> 
  <tr> 
   <td> <br></td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Problem Description 
    </div> 
    <div>
      Search is important in the acm algorithm. When you want to solve a problem by using the search method, try to cut is very important. 
     <br>Now give you a number sequence, include n (&lt;=100) integers, each integer not bigger than 2^31, you want to find the first P subsequences that is not decrease (if total subsequence W is smaller than P, than just give the first W subsequences). The order of subsequences is that: first order the length of the subsequence. Second order the subsequence by lexicographical. For example initial sequence 1 3 2 the total legal subsequences is 5. According to order is {1}; {2}; {3}; {1,2}; {1,3}. If you also can not understand , please see the sample carefully. 
    </div> 
    <div>
      &nbsp; 
    </div> <br></td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Input 
    </div> 
    <div>
      The input contains multiple test cases. 
     <br>Each test case include, first two integers n, P. (1&lt;n&lt;=100, 1&lt;p&lt;=100000). 
    </div> 
    <div>
      &nbsp; 
    </div> <br></td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Output 
    </div> 
    <div>
      For each test case output the sequences according to the problem description. And at the end of each case follow a empty line. 
    </div> 
    <div>
      &nbsp; 
    </div> <br></td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Sample Input 
    </div> 
    <div> 
     <pre>3 5
1 3 2
3 6
1 3 2
4 100
1 2 3 2</pre> 
    </div> 
    <div>
      &nbsp; 
    </div> <br></td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Sample Output 
    </div> 
    <div> 
     <pre>1
2
3
1 2
1 3

1
2
3
1 2
1 3

1
2
3
1 2
1 3
2 2
2 3
1 2 2
1 2 3</pre> 
     <div style="font-family:'Times     New Roman';font-size:14px;background-color:#f4fbff;border:#B7CBFF 1px dashed;"> 
      <div style="font-family:Arial;font-weight:bold;color:#7ca9ed;border-bottom:#B7CBFF 1px dashed;"> 
       <em>Hint</em> 
      </div> Hint : You must make sure each subsequence in the subsequences is unique 
     </div> 
     <div style="font-family:'Times     New Roman';font-size:14px;background-color:#f4fbff;border:#B7CBFF 1px dashed;">
       分析: 
     </div> 
     <div style="font-family:'Times     New Roman';font-size:14px;background-color:#f4fbff;border:#B7CBFF 1px dashed;">
       （1）这道题和前一题sequence one 属于一类题，都是dfs,这里主要是首先排一次顺序，然后再检查时注意输入时的下标，生成的子串不能够出现下表非递增的，也就是首先子串时递增的，其次下标也是递增的，然后不能有重复的子串出现。 
     </div> 
     <div style="font-family:'Times     New Roman';font-size:14px;background-color:#f4fbff;border:#B7CBFF 1px dashed;">
       （2）这是我的代码，和前一题的代码有稍微的改动，无奈一直wrong。。。。。。。。。。。。哪位研究这一题的看到了，帮忙找找错。。。。。。。。。 
     </div> 
     <div style="font-family:'Times     New Roman';font-size:14px;background-color:#f4fbff;border:#B7CBFF 1px dashed;">
       &nbsp; 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    using namespace std;
    
    //len:搜索的长度,count:记录有多少个串了
    int n,p,len,count_num,pre;
    
    //做一个标记，如果一个短的串都不能够找到，
    //那么就长的串就更不可能找到了，这里的一个巧妙地剪枝如果没用就会超时
    bool flag;
    
    typedef struct
    {
        int n,pos;
        int ind;
    }Tem;
    
    Tem tem[1001];
    Tem num[1001];
    
    bool cmp(Tem a,Tem b)
    {
        if(a.n==b.n)
        return a.pos<b.pos;
        return a.n<b.n;
    }
    //若在产生序列的前一个数字到当前这个数字中，
    //出现等于num[e]的，那么说明之前已经有序列选择了num[e]，
    bool check(int s,int e)
    {
        for(int i = e-1; i > s; i--)
        if(num[i].n==num[e].n)return false;
        return true;
    }
    
    
    void print_sequence(int length)
    {
        for(int i = 0; i < length-1;i++)
        printf("%d ",tem[i].n);
        printf("%d\n",tem[length-1].n);
    }
    
    //dep：搜索的深度，也就是目前搜索到子串的长度
    //pos: 当前搜索的位置
    void dfs(int dep,int pos)
    {
        if(count_num >= p)return;
        //搜索到了
        if(dep==len)
        {
            count_num++;
            flag = true;
            print_sequence(len);
            //已经搜索到符合的字串了
            return;
        }
        for(int i=pos;i<n;i++)
        {
            if((dep!=0&&num[i].pos>tem[dep-1].pos)||dep==0)
            {
                if(dep==0&&!check(-1,i))
                continue;
                if(dep!=0&&!check(tem[dep-1].ind,i))
                continue;
                tem[dep].n = num[i].n;
                tem[dep].pos = num[i].pos;
                tem[dep].ind = i;
                dfs(dep+1,i+1);
            }
        }
        return;
    }
    
    int main()
    {
        while(scanf("%d%d",&n,&p)!=EOF)
        {
            for(int i=0;i<n;i++)
            {
                scanf("%d",&num[i].n);
                num[i].pos = i;
            }
    
            sort(num,num+n,cmp);
            count_num = 0;
            for(int i = 1;i < n;i++)
            {
                flag=false;
                pre = 0;
                len = i;
                dfs(0,0);
                if(count_num>=p||!flag)break;
            }
            printf("\n");
        }
        return 0;
    }

这是我从网上找到达一个可以通过的代码。。。。。。

思路一样。。。。。。。求解释。。。。。。。

#include <cstdio>
    #include <queue>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    int n,p;
    
    struct Node
    {
            int pos;
            int v;
    };
    
    int cont;
    Node a[110];
    int res[10001];
    int deep;
    
    bool mcmp(const Node& x,const Node& y)
    {
            if(x.v != y.v)
                    return x.v < y.v;
            else
                    return x.pos < y.pos;
    };
    
    void init()
    {
            int i;
            int tv;
            cont = 0;
            Node tnode;
            for(i = 1;i <= n;i ++)
            {
                    scanf("%d",&tv);
                    a[i].pos = i;// 把位置作为结构题的一项
                    a[i].v = tv;
            }
            sort(a+1,a+1+n,mcmp);//按照值的大小重排序
    }
    
    bool dfs(int dep,int sp,int pp)//deepth ,search position , previous position
    {
            int i;
            int prev;
            bool f = false;
            if(dep == deep+1)
            {
                    cont ++;
                    for(i = 1;i < dep;i ++)
                            printf(i == deep ? "%d\n" : "%d ",res[i]);
                    if(cont == p) return true;
                    return false;
            }
    
            if(sp > n ) return false;
    
            for(i = sp;i <= n;i ++)
            {
                    if(a[i].pos > pp)
                    {
                            if(!f) { f = true; prev = a[i].v;} // 判重
                            else        if(prev == a[i].v) continue;//判重
                            prev = a[i].v;
                            res[dep] = a[i].v;
                            if(dfs(dep+1,i+1,a[i].pos) ) return true;
    
                    }
            }
            return false;
    }
    
    void work()
    {
            int i,j;
            for(i = 1;i <= n;i ++)
            {
                    deep = i;
                    if(dfs(1,1,0)) return ;
            }
    }
    
    int main()
    {
            while(scanf("%d%d",&n,&p) != EOF)
            {
                    init();
                    work();
                    printf("\n");
            }
    
            return 0;
    }