Create Number (CN)
強大的CN進化史 將呈列許多 ? 的作法
以下為最原始的生成組合+二分搜尋+插入排序
/************************************************************/
#include<stdio.h>
#include<stdlib.h>
int n,m;
int different[1000000],input[50],top;
int Search(int n,int L,int find[])
{
int lower=0, mid, high=L-1;
int index=-1;
do /*二分搜尋*/
{
mid=(lower+high)/2;
if(find[mid]<n) lower=mid+1;
else if(find[mid]>n) high=mid-1;
else index=mid;
}
while(index==-1&&lower<=high);
return index;
}
void check(int data)
{
int index=Search(data,top,different);
if(index==-1)
{
int a;
for(a=top-1;a>=0;a--)
if(data<different[a])
different[a+1]=different[a];
else break;
different[a+1]=data;
top++;
}
}
void make (int now,int a,int n,int SUM)
{
int b=a;
if(now>1)
check(SUM);
for(b=a;b<=n;b++)
make(now+1,b+1,n,SUM+input[b]);
}
main()
{
while(scanf("%d",&n)==1)
{
int a,b,c;
for(a=1;a<=n;a++)
scanf("%d",&input[a]);
for(a=1;a<=n;a++)
{
c=a;
for(b=a+1;b<=n;b++)
if(input[b]<input[c]) c=b;
int temp;
temp=input[a];
input[a]=input[c];
input[c]=temp;
}
top=0;
make(1,1,n,0);
for(a=0;a<top;a++) different[a]=0;
printf("%d\n",top);
}
return 0;
}
/**********************************************************/
以下程式碼為 a13032002 提供的DP想法
/**********************************************************/
#include<stdio.h>
#include<stdlib.h>
int n,m;
int different[1000000]={0},input[50],top;
int Search(int n,int L)
{
int lower=0, mid, high=L-1;
int index=-1;
do /*二分搜尋*/
{
mid=(lower+high)/2;
if(different[mid]<n) lower=mid+1;
else if(different[mid]>n) high=mid-1;
else index=mid;
}
while(index==-1&&lower<=high);
return index;
}
void check(int data)
{
int index=Search(data,top);
if(index==-1)
{
int a;
for(a=top-1;a>=0;a--)
if(data<different[a])
different[a+1]=different[a];
else break;
different[a+1]=data;
top++;
}
}
main()
{
while(scanf("%d",&n)==1)
{
int a,b,c;
top=1;
for(a=1;a<=n;a++)
{
scanf("%d",&input[a]);
int M=top,NEW[50000],Ntop=0;
for(b=0;b<M;b++)
NEW[Ntop++]=different[b]+input[a];
for(b=0;b<M;b++)
check(NEW[b]);
}
printf("%d\n",top-1);
}
return 0;
}
/**********************************************************/
以下作法 利用二元搜尋樹 代替二分搜尋+插入排序
但由於生成出來的數長得不好 所以速度小於上面的
(此時未習得平衡)
/**********************************************************/
#include<stdio.h>
#include<stdlib.h>
int n,m;
int link[50000][2]={0},NUM[50000]={0},top;
void Tree(int now,int value)
{
if(value>NUM[now])
{
if(link[now][1]==0)
link[now][1]=++top,NUM[top]=value;
else
Tree(link[now][1],value);
}
else if(value<NUM[now])
{
if(link[now][0]==0)
link[now][0]=++top,NUM[top]=value;
else
Tree(link[now][0],value);
}
}
main()
{
while(scanf("%d",&n)==1)
{
int a,b,c,M;
for(a=0;a<top;a++)
link[a][0]=0,link[a][1]=0,NUM[a]=0;
top=1;
for(a=1;a<=n;a++)
{
scanf("%d",&m);
M=top;
for(b=1;b<=M;b++)
Tree(1,m+NUM[b]);
}
printf("%d\n",top-1);
}
return 0;
}
/**********************************************************/
習得平衡之後 速度成為之中最快的28 ms 但是仍比HASH慢...
/**********************************************************/
#include<stdio.h>
#include<stdlib.h>
int n,m;
int link[50000][2]={0},NUM[50000]={0},top,MAX;
void Tree(int now,int value,int L)
{
if(MAX<L) MAX=L;
if(value>NUM[now])
{
if(link[now][1]==0)
link[now][1]=++top,NUM[top]=value;
else
Tree(link[now][1],value,L+1);
}
else if(value<NUM[now])
{
if(link[now][0]==0)
link[now][0]=++top,NUM[top]=value;
else
Tree(link[now][0],value,L+1);
}
}
int s[50000],stop=0;
void treesort(int now)
{
if(link[now][0]!=0) treesort(link[now][0]);
s[stop++]=NUM[now];
if(link[now][1]!=0) treesort(link[now][1]);
}
void putin(int l,int h,int flag)
{
if(l>h) return;
int m=(l+h)/2;
if(flag==1) NUM[1]=s[m];
else Tree(1,s[m],0);
putin(l,m-1,0);
putin(m+1,h,0);
}
void balance()
{
stop=0,top=1;
treesort(1);
int a;
for(a=0;a<=stop;a++) link[a][0]=0,link[a][1]=0,NUM[a]=0;
putin(0,stop-1,1);
}
main()
{
while(scanf("%d",&n)==1)
{
int a,b,c,M;
for(a=0;a<top;a++)
link[a][0]=0,link[a][1]=0,NUM[a]=0;
top=1;
for(a=1;a<=n;a++)
{
scanf("%d",&m);
M=top,MAX=0;
for(b=1;b<=M;b++)
Tree(1,m+NUM[b],0);
if(MAX>50) balance();
}
printf("%d\n",top-1);
}
return 0;
}
上一篇:快速排序. (非快排版)
下一篇:複數比大小