2.剪枝是搜索的关键?
3.可贪则贪?
4.枚D是最Ҏ实现的,但也是最慢的?
5.N往往需要另辟蹊径?
6.法q不是孤立的Q而是可以l合在一L?
7.不做烂题水^也会下降Q但不想N永远不会提高?/div>
]]>
q也是一个很单的递归问题Q?span> L[n] = L[n-1] + n; (L[0] = 1)
通项公式如下Q?span>L[n] = n * (n + 1) / 2 + 1 ( n>= 0 )
如果不用直线的话Q用一个一般的折线Q那?span>n个这L折线最多可以拆分^?span>:
D[n] = L[2*n] - 2 * n;
D[n] = 2 * n ^ 2 - n + 1;
如果?span>"Z"字型的线Q?span>n个折U最可拆分^面:
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=652
Z[n] = Z[n-1] + 9*n - 8;
Z[n] = (9*n^2 - 7*n + 2) / 2;
2 int main()
3 {
4 int n;
5 while(scanf("%d",&n)!=EOF){
6 printf("%d\n",(9*n*n-7*n+2)/2);
7 }
8 return 0;
9 }
]]>
同时一?/span>n行三角ŞT?/span>+Q?/span>-号个数分别记?/span>pos_num(n),neg_num(n)Q其W一行中?/span>+Q?/span>-号个数记?/span>x(n),y(n)Q则可得C式:
pos_num(n)=x(n)+pos_num(n-1)
neg_num(n)=y(n)+neg_num(n-1)
由此Q我们可以从n=1开始,利用前面n=k-1的结果,q代求出n=k的分布情形,然后?/span>n=k的所有分布统计?br>
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
struct record
{
int pos,neg;
record(int a,int b)
{
pos=a; neg=b;
}
};
int main()

{
int n,i,j,k,sum;vector<record> v;
for(int m=1;m<=24;m++)
{
n=m;
if((n*(n+1))%4!=0)
{
cout<<n<<" 0"<<endl;
continue;
}
vector<record> v;
record r1(0,1);//n=1的情?/span>
v.push_back(r1);
record r2(1,0);
v.push_back(r2);
for(i=2;i<=n;i++)//计算到n的所有情?/span>
{
int * trip=new int[i];
int sum_i=(int)pow(2.0,i*1.0);
for(j=0;j<sum_i;j++)//WjU分?/span>
{
int temp1=j, temp2=i;
int x=0, y=0; //记录+Q?的个?/span>
while(temp1)
{
if(temp1%2==0)
{
trip[--temp2]=0; y++;
}
else
{
trip[--temp2]=1; x++;
}
temp1/=2;
}
for(k=0;k<temp2;k++)
y++, trip[k]=0;
int idx=0;
for(k=0;k<i-1;k++)
{
if(trip[k]+trip[k+1]==1)
idx*=2;
else idx*=2,idx+=1;
}
x+=v[2*((int)pow(2.0,i-2.0)-1)+idx].pos;
y+=v[2*((int)pow(2.0,i-2.0)-1)+idx].neg;
record r(x,y);
v.push_back(r);
}
}
/**//*if(n==3){
int star=2*((int)pow(2.0,n-1.0)-1);
for(j=0;j<(int)pow(2.0,n*1.0);j++)
printf("---%d %d\n",v[star+j].pos,v[star+j].neg);
}*/
int base=2*((int)pow(2.0,n-1.0)-1);
int num=(int)pow(2.0,n*1.0);
sum=0;
for(i=0;i<num;i++)
{
if(v[base+i].pos==v[base+i].neg)
sum++;
}
cout<<n<<" "<<sum<<endl;
}
return 0;
}题中Q?/span>n<=24Q时间空间均有限Ӟ我们可以先求出所有结果,然后保存到数l直接取来输出。这?/span>ACM题中很常见的情况?/span>
2 int res[25]={0,0,0,4,6,0,0,12,40,0,0,171,410,
3 0,0,1896,5160,0,0,32757,59984,0,0,431095,822229};
4 int main()
5 {
6 int n;
7 while(scanf("%d",&n),n)
8 {
9 printf("%d %d\n",n,res[n]);
10 }
11 return 0;
12 }
]]>


