| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
C语言 AC代码 dfs#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int m,n,x[102]={0},total=0,cnt=0,ans[1002]={0},k,c=0,ans2[2000][100]={{0}},num[2000]={0};
void dfs(int a,int b)
{
int a0,b0,i;
if (b==0)
{
total++;
for (k=0;k<=cnt-1;k++)
ans2[c][k]=ans[k];
num[c]=cnt;
c++;
}
for (i=a+1;i<=m-1;i++)
{
b0=b-x[i];
if (b0>=0)
{
ans[cnt]=x[i];
cnt++;
a0=i;
dfs(a0,b0);
cnt--;
}
}
}
int main()
{
int j,i0,j0=0,p[1000],k0;
do{
scanf("%d%d",&n,&m);
if (n==0)
break;
total=0;
memset(ans2,0,sizeof(ans2));
memset(ans,0,sizeof(ans));
cnt=0;
c=0;
for (j=0;j<=m-1;j++)
scanf("%d",&x[j]);
dfs(-1,n);
memset(p,1,sizeof(p));
for (i0=0;i0<=total-1;i0++)
{
if (!p[i0])
continue;
for (j0=i0+1;j0<=total-1;j0++)
{
if (!p[j0])
continue;
if (num[i0]==num[j0])
{
for (k0=0;k0<=num[i0]-1;k0++)
{
if (ans2[i0][k0]!=ans2[j0][k0])
{
p[j0]=1;
goto l1;
}}
p[j0]=0;
l1: ;
}
}
}
printf("Sums of %d:\n",n);
if (total==0)
printf("NONE\n");
else
{
for (i0=0;i0<=total-1;i0++)
{
if (p[i0])
{
for (j0=0;j0<=num[i0]-2;j0++)
{
printf("%d+",ans2[i0][j0]);
}
printf("%d",ans2[i0][num[i0]-1]);
printf("\n");
}
}
}
}while(1);
return 0;
}
注意判重,多用前面评论里的陷阱数据试试
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator