hdu 1016 && zoj 1457 Prime Ring Problem (dfs)

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1457

 

解题报告：在zoj第一次提交的时候竟然是TLE,让我很是费解，然后把判断素数的方法变成直接打表的方法 ，以为这样可以节省很多的时间，结果还是TLE(hdu上此时就可以Ac),后来试了一下数字19，结果很久都没有跑出结果，感觉应该是这的问题，我就把奇数与偶数分开，结果AC。（感觉杭电的数据弱爆了）

 

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

const int MAX =20+5;
int vis[MAX],path[MAX],n;

int Isprim[42] = {0,1,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1};

void dfs(int cnt)
{
	if(cnt<=n)
	{
		int num=path[cnt];
		for(int i=2;i<=n;i++)
		{
			if(!vis[i]&&Isprim[i+num])
			{
				path[cnt+1]=i;
				vis[i]=1;
				dfs(cnt+1);
				vis[i]=0;
			}
		}
	}
	if(cnt==n&&Isprim[path[1]+path[n]])
	{
		for(int i=1;i<n;i++)
			printf("%d ",path[i]);
		printf("%d\n",path[n]);
	}
}

int main()
{
	int ncase=0;
	while(scanf("%d",&n)!=EOF)
	{
		printf("Case %d:\n",++ncase);
		memset(vis,0,sizeof(vis));
		path[1]=vis[1]=vis[0]=1;
		if(n%2 == 0)//不判段就是tle
		dfs(1);
		printf("\n");
	}
	return 0;
}