http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=579#problem/D
题意:给出一段数,每相邻两个数字之间用+,-,*,/四个符号中的一个,忽略乘除的优先级,优先顺序为从左到右,
问如何安排符号使最后的结果最大,并且sum的最后结果每位数字不能含有k
分析:DFS~~
这道题很水,但是如果队友不指出错误的话,依旧找不到错在哪,很明显,在判断每位数字的时候,若sum=0的话循环进不去,这时候
若k也等于0,就会返回true,而正确应该是false
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int MN=20;
long long num[MN];
long long ans;
long long n,k;
bool OK(long long sum)//若sum=0的话,循环是不会进去的
{
if(sum==0 && k==0) return false;
if(sum==0 && k!=0) return true;
while(sum)
{
if(sum%10==k) return false;
sum/=10;
}
return true;
}
void DFS(int cur,long long sum)
{
if(cur==n-1)
{
if(sum>ans && OK(sum)) ans=sum;
return ;
}
DFS(cur+1,sum+num[cur+1]);
DFS(cur+1,sum*num[cur+1]);
if(sum>num[cur+1]) DFS(cur+1,sum-num[cur+1]);
else DFS(cur+1,num[cur+1]-sum);
if(num[cur+1]!=0) DFS(cur+1,sum/num[cur+1]);
}
int main()
{
int i,j,T;
while(scanf("%d",&T)!=EOF)
{
while(T--)
{
scanf("%lld%lld",&n,&k);
ans=-10;
for(i=0; i<n; i++)
{
scanf("%lld",&num[i]);
}
DFS(0,num[0]);
if(ans<0) printf("No result\n");
else printf("%lld\n",ans);
}
}
return 0;
}