hdu 1342+hdu 2660+hdu 2266+hdu 1704+hdu 1627+hdu 1539

几道搜索水题，搜索要点就是不断剪枝，必要时还要不断恢复路径。

慢慢体会递归的强大！！！

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1342

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 55
int num[MAXN];
int path[MAXN];
int k,len;

void dfs(int x,int cnt){
    path[len++]=num[x];
    if(cnt==6){
        printf("%d",path[0]);
        for(int i=1;i<len;i++)printf(" %d",path[i]);
        puts("");
        return ;
    }
    for(int i=x+1;i<=k;i++){
        dfs(i,cnt+1);
        len--;
    }
}

int main(){
    int t=0;
    while(~scanf("%d",&k)&&k){
        if(t++)puts("");
        for(int i=1;i<=k;i++)scanf("%d",&num[i]);
        for(int i=1;i<=k;i++){
            len=0;
            dfs(i,1);
        }
    }
    return 0;
}

 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2660

这道题也可以用背包解。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 22
struct Node{
    int v,w;
}node[MAXN];

int W,n,k,ans;

void dfs(int i,int value,int weight,int count){
    if(count==k){
        ans=max(ans,value);
        return ;
    }
    for(int j=i+1;j<=n;j++){
        if(weight+node[j].w<=W)dfs(j,value+node[j].v,weight+node[j].w,count+1);
    }
}

int main(){
    int _case;
    scanf("%d",&_case);
    while(_case--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++){
            scanf("%d%d",&node[i].v,&node[i].w);
        }
        scanf("%d",&W);
        ans=0;
        for(int i=1;i<=n;i++){
            if(node[i].w<=W)dfs(i,node[i].v,node[i].w,1);
        }
        printf("%d\n",ans);
    }
    return 0;
}

 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2266

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
typedef long long ll;

#define MAXN 14
ll sum,cnt;
int len;
char str[MAXN];

//递归的强大！！！
void dfs(int pos,ll s){
    if(pos==len&&s==sum){
        cnt++;
        return ;
    }
    ll tmp=0;
    for(int i=pos;i<len;i++){
        tmp=tmp*(ll)10+str[i]-'0';
        dfs(i+1,s+tmp);
        if(pos!=0)dfs(i+1,s-tmp);//不知为什么，pos改成i就错了。
    }
}

int main(){
    while(~scanf("%s",str)){
        scanf("%I64d",&sum);
        cnt=0,len=strlen(str);
        dfs(0,0);
        printf("%d\n",cnt);
    }
    return 0;
}

 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1704

这道题也可以用传递闭包来做。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define MAXN 555
vector<int>vt[MAXN];
int n,m;

bool dfs(int x,int y){
    for(int i=0;i<vt[x].size();i++){
        int u=vt[x][i];
        if(u==y)return true;
        if(dfs(u,y))return true;
    }
    return false;
}

int main(){
    int _case,u,v;
    scanf("%d",&_case);
    while(_case--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)vt[i].clear();
        for(int i=1;i<=m;i++){
            scanf("%d%d",&u,&v);
            vt[u].push_back(v);
        }
        int cnt=0;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(!(dfs(i,j)||dfs(j,i)))cnt++;
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1627

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 111
int path[MAXN];
int n,l,cnt;

bool dfs(int cur){
    if(n==cnt){
        int k=0,num=0;
        for(int i=0;i<cur;i++){
            if(k==4&&num!=16){printf(" ");k=0;}
            if(num==16){puts("");num=0,k=0;}
            printf("%c",path[i]+'A');
            k++;
            if(k==4)num++;
        }
        puts("");
        printf("%d\n",cur);
        return true;
    }
    for(int i=0;i<l;i++){
        path[cur]=i;
        bool flag=false;
        for(int j=1;j<=(cur+1)/2;j++){
            flag=true;
            for(int k=0;k<j;k++){
                if(path[cur-k]!=path[cur-j-k]){flag=false;break;}
            }
            if(flag)break;
        }
        if(flag)continue;
        cnt++;
        if(dfs(cur+1))return true;
    }
    return false;
}


int main(){
    while(~scanf("%d%d",&n,&l)){
        if(n==0&&l==0)break;
        memset(path,-1,sizeof(path));
        cnt=0;
        dfs(0);
    }
    return 0;
}

 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1539

对这道题略无语，测试数据都说了不超过6位，我开了11位，wa无数次，最后搞了个22位的过了。。。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 22//不是说测试数据不超过6位吗！！！一开始搞了个11的还过不了！！！！
char str[MAXN];
int n,len,relen,ans,l,tag;
int path[MAXN];
int repath[MAXN];

//递归+路径保存！！！
void dfs(int pos,int sum){
    if(sum>n)return ;
    if(pos==len){
        if(sum<=n&&sum>=ans){
            if(sum==ans)tag=2;//有多个最接近的值,就rejected
            else {
                ans=sum,relen=0,tag=1;
                for(int i=0;i<l;i++)repath[relen++]=path[i];
            }
        }
        return ;
    }
    int tmp=0;
    for(int i=pos;i<len;i++){
        tmp=tmp*10+str[i]-'0';
        path[l++]=tmp;
        dfs(i+1,sum+tmp);
        l--;
    }
}



int main(){
    while(~scanf("%d%s",&n,str)){
        if(n==0&&str[0]=='0')break;
        len=strlen(str);
        ans=0,l=0,tag=0;
        memset(path,0,sizeof(path));
        memset(repath,0,sizeof(repath));
        dfs(0,0);
        if(tag==0)puts("error");//都大于n就是error了。
        else if(tag==2)puts("rejected");
        else {
            printf("%d",ans);
            for(int i=0;i<relen;i++)printf(" %d",repath[i]);
            printf("\n");
        }
    }
    return 0;
}