ZOJ 1204 Additive equations
2017年10月03日
⁄ 综合
⁄ 共 1571字 ⁄ 字号
小 中 大
-
地址：http:
-
-
题意
-
-
按顺序输出相加等于in[]的所有组情况
-
Sample Input
-
3
-
3 1 2 3
-
3 1 2 5
-
6 1 2 3 5 4 6
-
Output for the Sample Input
-
1+2=3
-
-
Cant find any equations.
-
-
1+2=3
-
1+3=4
-
1+4=5
-
1+5=6
-
2+3=5
-
2+4=6
-
1+2+3=6
-
-
解题思路
-
-
简单的DFS。因为时间有10s，所以我用了一个蠢办法，控制answer-算式的长度，从而实现按题要求输出。
-
-
代码
-
-
#include <stdio.h>
-
#include <stdlib.h>
-
#include <string.h>
-
int comp(const void *a,const void *b)
-
{
-
return *(int*)a-*(int*)b;
-
}
-
#define max 505
-
int in[max];
-
int vis[max];
-
int n,flag;
-
int all;
-
int find(int sum)
-
{
-
int x;
-
for(x=0;x<n;x++)
-
if(in[x]==sum)
-
return 1;
-
return 0;
-
}
-
-
void dfs(int x,int sum,int len)
-
{
-
int i,a;
-
if(find(sum)&&len==all)
-
{
-
int ans[max];
-
int j=0;
-
for(a=0;a<max;a++)
-
{
-
if(vis[a]!=0)
-
ans[j++]=a;
-
}
-
if(j>1)
-
{
-
for(a=0;a<j-1;a++)
-
printf("%d+",in[ans[a]]);
-
printf("%d=%d\n",in[ans[a]],sum);
-
flag=1;
-
}
-
}
-
for(i=x;i<n;i++)
-
{
-
if(vis[i]==0&&(sum+in[i])<=in[n-1])
-
{
-
vis[i]=1;
-
dfs(i+1,sum+in[i],len+1);
-
vis[i]=0;
-
}
-
}
-
}
-
-
int main()
-
{
-
int t,i;
-
scanf("%d",&t);
-
while(t--)
-
{
-
scanf("%d",&n);
-
for(i=0;i<n;i++)
-
scanf("%d",&in[i]);
-
qsort(in,n,sizeof(in[0]),comp);
-
flag=0;
-
for(all=1;all<=n;all++)
-
{
-
memset(vis,0,sizeof(vis));
-
dfs(0,0,0);
-
}
-
if(flag==1)
-
{
-
printf("\n");
-
}
-
else
-
printf("Can't find any equations.\n\n");
-
}
-
return 0;
-
}