http://poj.org/problem?id=1426 bfs:剛剛拿到想把所有數(shù)給用字符串保存，這樣最多可有100個(gè)01呢。
一直都覺得這樣樸素的算法很惡心，就去吃飯去了，我嚓，12點(diǎn)吃早飯。
突然想到其實(shí)我的串可以que[]里存0和1嘛，然后索引一下就好了于是乎，行了，嘿嘿。這樣遞推過去的，其實(shí)應(yīng)該是可以整出了dp狀態(tài)轉(zhuǎn)移方程的哈，等會(huì)想想呢
bfs:
32MS
#include<stdio.h>
#include<string.h>
#include<math.h>
int n;
int que[1000005],pre[1000005],q[1000005],ans[205];//que[] 0、1，q[]當(dāng)前余數(shù)，pre[]前驅(qū)。
int bfs()
{
int head,tail,now,next,i;
head=0;tail=1;que[1]=1;pre[1]=0;q[1]=1;
while (head<tail)
{
now=q[++head]*10;
for (i=0;i<=1 ;i++ )
{
next=now+i;
tail++;
que[tail]=i;
q[tail]=next%n;
pre[tail]=head;
if (!q[tail])
return tail;
}
}
}
int main()
{
int i,k;
while (scanf("%d",&n)==1&&n)
{
i=bfs();
k=0;
while (i)
{
ans[++k]=que[i];
i=pre[i];
}
for (i=k;i>=1 ;i-- )
printf("%d",ans[i]);
printf("\n");
}
return 0;
}
同學(xué)用的long long 也過了，容我研究研究哈。
long long:我暈，居然跑了110MS
#include<stdio.h>
#include<string.h>
#include<math.h>
int n;
long long ans,now,que[1000005];
int bfs()
{
int head,tail,i;
head=0;tail=1;
que[1]=1;
while (head<tail)
{
now=que[++head];
for (i=0;i<=1 ;i++ )
{
ans=now*10+i;
if (ans%n==0)
return;
tail++;
que[tail]=ans;
}
}
}
int main()
{
while (scanf("%d",&n)==1&&n)
{
bfs();
printf("%I64d\n",ans);
}
return 0;
}
dp會(huì)跑多久么？