dfs Gym - 100989L
AbdelKader enjoys math. He feels very frustrated whenever he sees an incorrect equation and so he tries to make it correct as quickly as possible!
Given an equation of the form: A1 o A2 o A3 o ... o An = 0, where o is either + or -. Your task is to help AbdelKader find the minimum number of changes to the operators + and -, such that the equation becomes correct.
You are allowed to replace any number of pluses with minuses, and any number of minuses with pluses.
Input
The first line of input contains an integer N (2 ≤ N ≤ 20), the number of terms in the equation.
The second line contains N integers separated by a plus + or a minus -, each value is between 1 and 108.
Values and operators are separated by a single space.
Output
If it is impossible to make the equation correct by replacing operators, print - 1, otherwise print the minimum number of needed changes.
Examples
7
1 + 1 - 4 - 4 - 4 - 2 - 2
3
3
5 + 3 - 7
-1 题目翻译:一串数字改变其的符号,让sum为0,输出最小的改变次数,不存在则输出-1 运用算法DFS ac代码:
#include<iostream>
using namespace std;
int a[25],n,ans;
void dfs(int index,int sum,int c)
{
if (index==n+1){
if (sum==0){
ans=ans<c?ans:c;
}
return ;
}
int j;
for (j=0;j<2;j++){ //只存在 + 或者是 - 两种情况
if (j==0){
if (a[index]<0)
dfs(index+1,sum-a[index],c+1);
else
dfs(index+1,sum+a[index],c);
}
else if (a[index]<0)
dfs(index+1,sum+a[index],c);
else
dfs(index+1,sum-a[index],c+1);
}
return ;
}
int main()
{
//scanf("%d",&n);
char op;
int i,j;
ans=99999999;
cin>>n;
for (i=1;i<=n;i++){
if (i==1)
scanf("%d",&a[i]);
else{
scanf(" %c %d",&op,&a[i]);
if (op=='-')
a[i]=-a[i];
}
}
dfs(2,a[1],0);
if (ans==99999999)
cout<<"-1\n";
else
cout<<ans<<endl;
return 0;
}
最新文章
- 01-Swift 介绍
- 百度上传工具webuploader,图片上传附加参数
- javax.servlet.ServletException: com.microsoft.jdbc.base.BaseDatabaseMetaData.supportsGetGeneratedKeys()Z
- Laravel 5 基础(十一)- Eloquent 关系
- EF6 在原有数据库中使用 CodeFirst 总复习(二、新的需求,简单修改原有表)
- js amd
- iOS不越狱装收费App——注册iOS设备为开发者工具
- c# 的导入功能SqlBulkCopy
- [置顶] ./build_native 时出现please define NDK_ROOT
- 【数学水题】【TOJ4113】【 Determine X】
- TxDragon的训练5
- Linux 下的权限改变与目录配置
- 【2019雅礼集训】【CF 960G】【第一类斯特林数】【NTT&;多项式】permutation
- bat 传递参数
- lumen框架学习01——引入自定义类和函数
- .net mvc 分页
- sqlplus连接远程数据库
- Python小项目四:实现简单的web服务器
- [2017BUAA软工助教]学期总结
- laravel5.3之后可以使用withCount()这个方法