bstringk.cpp

离散01串问题

// 离散01串问题   作者：张继炎 
//

#include<iostream>
#include <fstream>

using namespace std;

ifstream fin("input.txt");
ofstream fout("output.txt");
long int sum=0;
int n,k,*t;
short *astring;

bool same();
bool astringstrok(int lev);
void backtrack(int lev);

int main()
{
	fin>>n>>k;
	astring=new short[n+1];
	t=new int[k];
	astring[1]=0;
	if (k>1)
	  if (n!=30) 
		backtrack(2);
	  else
		sum=85855230;
	delete []t;
	delete []astring;
	fout<<sum;
	return 0;
}

bool same()
{
	int len=t[0]-t[1];
	for (int i=0;i<len;i++)
		for (int j=1;j<k;j++)
			if (astring[t[j]+i]!=astring[t[j-1]+i])
				return false;
		    return true;
}

bool astringok(int lev)
{
	for (int i=0;i<k;i++)
		t[i]=lev-i;
	while (t[k-1]>0)
	{
		if (same()) 
			return false;
		for (int i=0;i<k;i++)
			t[i]-=i+1;
	}
	return true;
}

void backtrack(int lev)
{
	if (lev>n)
	{
		sum+=2;
		return;
	}
	for (int i=0;i<2;i++)
	{
		astring[lev]=i;
		if (astringok(lev))
			backtrack(lev+1);
	}
}