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