HDU 1016 Prime Ring Problem

时间：2014-02-10 16:32:27 收藏：0 阅读：340

简单DFS

#include <cstdio>
bool 
used[21];
bool 
prim[41];
int now[21];
int i,j,n;
 
void 
out()
{
    printf("1");
    for(int 
i=2;i<=n;i++) printf(" %d",now[i]);
    printf("\n");
}
 
void 
dfs(int 
step)
{
    if 
(step==n&&prim[now[n]+1]) out();//注意是==，=导致WA 
    for(int 
i=2;i<=n;i++)
    if 
((!used[i])&&(prim[i+now[step]]))
    {
        used[i]=true;
        now[step+1]=i;
        dfs(step+1);
        used[i]=false;
    }    
}
 
int 
main()
{
    int 
cnt=1;
    for 
(int i=2;i<21;i++)used[i]=false;
    for 
(int i=1;i<41;i++)prim[i]=true;
    for(int 
i=2;i<41;i++)
    {
        if(!prim[i]) continue;
        for(int 
j=2*i; j<41; j+=i)prim[j]=false;
    }
    now[1]=1; used[1]=true;
    while(scanf("%d",&n)!=EOF)
    {
        printf("Case %d:\n",cnt++);
        dfs(1);
        puts(""); 
    }
}

原文：http://www.cnblogs.com/forever97/p/3542418.html