64-bit integer IO format: Java class name:
15 16 19 20 0
15 1896 16 5160 19 32757 20 59984
开始 直接搜索都超时了，最后是搜索打表才ac的。
开始的搜索代码：
#include <iostream> #include<cstdio> #include<cmath> using namespace std; const int N=25; int n,a[N][N],c,h,sum; int js_1(int k,int s) { for(int i=0,j=k;i<k;i++,j--) { s+=a[i][j]; if(a[i][j-1]==a[i][j]) a[i+1][j-1]=1; else a[i+1][j-1]=0; } return s; } void dfs(int t,int js) { if(t>n) { c++; } else { for(int i=0;i<2;i++) { a[0][t]=i; int x=js_1(t,js); if(x<=h&&(t*(t+1))/2-x<=h) dfs(t+1,x); } } } int main() { while(scanf("%d",&n)!=EOF&&n) { c=0; sum=n*(n+1)/2; if(sum%2==0) { h=sum/2; dfs(1,0); } printf("%d %d\n",n,c); } }
AC的代码：
#include <iostream> using namespace std; int result[24]={0,0,4,6,0,0,12,40,0,0,171,410,0,0,1896,5160,0,0,32757,59984,0,0,431095,822229}; int main() { int n; cin>>n; while(n!=0) { cout<<n<<" "<<result[n-1]<<endl; cin>>n; } return 0; }
原文：http://www.cnblogs.com/fenhong/p/5264641.html