当前位置: 代码迷 >> 综合 >> poj 2558 Genetic Code 深搜+打表
  详细解决方案

poj 2558 Genetic Code 深搜+打表

热度:3   发布时间:2024-01-19 05:30:04.0

题意:

求一个长度为n的串n<=5000,它没有相邻且相同的子串。

分析:

一开始各种构造,后来发现可以深搜,输出结果的时候打表就可以了,原来O(3^5000)的程序也不是一定会超时的。。只要剪枝吊,照样可以搞。。

代码:

//poj 2558
//sep9
#include <iostream>
using namespace std;
const int maxN=5000;
int n,ok,a[maxN+10];bool check(int cur)
{for(int len=1;len<=(cur+1)/2;++len){int p=cur-2*len+1;int q=cur-len+1;while(a[p]==a[q]&&q<=cur)++p,++q;if(q>cur)return false;	}return true;		
}void dfs(int cur)
{if(cur>maxN){ok=1;return ;}for(int i=0;i<3&&!ok;++i){a[cur]=i;if(check(cur))dfs(cur+1);}	
}int main()
{ok=0;dfs(0);while(scanf("%d",&n)==1&&n){for(int i=0;i<n;++i)if(a[i]==0) putchar('N');else if(a[i]==1) putchar('O');else putchar('P');		puts("");}return 0;	
} 


  相关解决方案