注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

【搜索】【DFS】 hdu 2611 Sequence two  

2011-11-10 11:35:41|  分类: ACM_搜索 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=2611
题目大意:
你懂的
分析:
很裸的dfs搜索,
从深度为1到n dfs搜索遍历,找满足条件的序列,注意判重,
数据存储的时候用了一个结构体,
struct Node
{
        int pos;//数据的位置
        int v;//数据的值
};

然后按照值从小到大排序,在这个基础上dfs搜索,

注意:刚开始做的时候只是用int数组存储数据的,结果就不知到怎么做了,因为需要按照题目要求的顺序输出,后来想到结构体,有种Map_Reduce的感觉~有木有~
想好解题的数据结构很重要

代码:
#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;
}




  评论这张
 
阅读(361)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018