[水+dfs] poj 2034 Anti

题意：

给n，m，，k。

排列n~m之间的所有数。

保证相邻的2~k位之和均不为素数。

思路：

直接DFS。

代码：

#include"cstdlib"#include"cstdio"#include"cstring"#include"cmath"#include"queue"#include"algorithm"#include"iostream"#include"map"#include"stack"#include"vector"#define ll __int64#define inf -999999999999999999LLusing namespace std;#define MAXN 100007bool mark[MAXN];int ss[MAXN/3],sscnt;int n,m,d,f;int sum[1234],a[1234],used[1234];void ssb(){sscnt=0;memset(mark,false,sizeof(mark));mark[0]=mark[1]=true;for(int i=2; i<=MAXN; i++){if(!mark[i]){for(int j=i+i; j<=MAXN; j+=i) mark[j]=true;ss[sscnt++]=i;}}return ;}void dfs(int x){if(f) return;if(x>m-n+1){f=1;return ;}for(int i=n;i<=m;i++){if(!used[i]){int kx=1;for(int j=2;j<=d && x-j>=0;j++){if(mark[sum[x-1]-sum[x-j]+i]==false) kx=0;}if(!kx) continue;sum[x]=sum[x-1]+i;a[x]=i;used[i]=1;dfs(x+1);if(f) return;used[i]=0;}}}int main(){ssb();while(scanf("%d%d%d",&n,&m,&d),(n+m+d)){f=0;memset(sum,0,sizeof(sum));memset(used,0,sizeof(used));dfs(1);if(!f) puts("No anti-prime sequence exists.");else for(int i=1;i<=m-n+1;i++) printf(i==m-n+1?"%d\n":"%d,",a[i]);}return 0;}

将会错过更好的风景，保持一份平和，保持一份清醒。