http://poj.org/problem?id=1426 bfs:刚刚拿到想把所有数给用字符串保存，这样最多可有100个01呢。
一直都觉得这样朴素的算法很恶心，就去吃饭去了，我嚓，12点吃早饭。
突然想到其实我的串可以que[]里存0和1嘛，然后索引一下就好了于是乎，行了，嘿嘿。这样递推过去的，其实应该是可以整出了dp状态转移方程的哈，等会想想呢
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[]当前余数，pre[]前驱。
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;
}
同学用的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会跑多久么？