DFS（8）——poj2034Anti-prime Sequences

一、题目回顾

题目链接：Anti-prime Sequences

Sample Input

1 10 2

1 10 3

1 10 5

40 60 7

0 0 0

 

Sample Output

1,3,5,4,2,6,9,7,8,10

1,3,5,4,6,2,10,8,7,9

No anti-prime sequence exists.

40,41,43,42,44,46,45,47,48,50,55,53,52,60,56,49,51,59,58,57,54

题意：求n到m的一个排列，满足任意连续的k(2<=k<=d)个数的和都不为素数。

二、解题思路

• dfs+素数打表

三、代码

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

const int maxn = 10001;

int ans[1001];

int n,m,d,flag;

int prime[maxn];

bool vis[1001];

void isPrime()

{

/*	memset(prime,1,sizeof(prime));

    prime[1] = 0;

    for (int i=2;i<=10000;i++)

        if (prime[i])

			for (int j=i+i;j<=10000;j+=i)

				prime[j] = 0;*/

	for(int i=2;i<maxn;i++)

		for(int j=2;i*j<maxn;j++)

	    	prime[i*j]=1;

}

void dfs(int now)

{

	if(flag)	return;

	if(now>m-n+1){

		flag = 1;

		return;

	}

	for(int i=n;i<=m;i++){

		int biaoji = 0;

		if(!vis[i]){

			for(int j=2;j<=d&&now-j>=0;j++){

				if(!prime[ans[now-1]+i-ans[now-j]])

            		biaoji = 1;

			}

			if(biaoji)	continue;

			ans[now] = ans[now-1] + i;

			vis[i] = 1;

			dfs(now+1);

			if(flag)	return;

			vis[i] = 0;

		}

	}

}

int main()

{

	isPrime();

	while(cin>>n>>m>>d && !(n==0&&m==0&&d==0)){

		memset(vis,0,sizeof(vis));

		flag = 0;

		dfs(1);

		if(flag==0)	printf("No anti-prime sequence exists.\n");

		else{

			printf("%d",ans[1]);

        	for(int i=2;i<=m-n+1;i++)

        		printf(",%d",ans[i]-ans[i-1]);

        	printf("\n");

		}

	}

	return 0;

}