George met AbdelKader in the corridor of the CS department busy trying to fix a group of incorrect equations. Seeing how fast he is, George decided to challenge AbdelKader with a very large incorrect equation. AbdelKader happily accepted the challenge!
Input
The first line of input contains an integer N (2 ≤ N ≤ 300), 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 300.
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
Input
7
1 + 1 - 4 - 4 - 4 - 2 - 2
Output
3
Input
3
5 + 3 - 7
Output
-1
题意：给你一个表达式（只包括数字，符号（“+”或“-”）），问你是否能改变最少的符号使得表达式值为0.
思路：看到这题，一开始就用dfs做，但是因为数据量太大没过，后来听学长讲才知道这道题可以用背包做。。。。
背包选择范围（0---sum），我们以sum/2+s[1]为起点，sum/2为终点，因为当我们已经选择变化的和不能超过sum/2（因为绝对值的和才sum，如果你选的超过了一半，那么无论后面怎么选择总和都不可能为0）；
代码：
#include<stdio.h>
#define INF 0x3fffffff
#include<string.h>
int dp[2][90000];
int s[305];
int min(int a,int b){
if(a<b)
return a;
return b;
}
int main(){
int n;
scanf("%d",&n);
int i,j;
int sum=0;
scanf("%d",&s[1]);
sum=s[1]; char b;
for(i=2;i<=n;i++){
getchar();
scanf("%c %d",&b,&s[i]);
sum=sum+s[i];
if(b=='-')
s[i]=-s[i];
}
if(sum%2==1)
printf("-1\n");
else{
int a,b;
a=1;
memset(dp[!a],0x3f,sizeof(dp[!a]));
dp[0][sum/2+s[1]]=0;//如果选择的总数和超过了sum/2，它就回不来了
for(i=2;i<=n;i++){
memset(dp[a],0x3f,sizeof(dp[a]));
for(j=0;j<=sum;j++){
if(j-s[i]>=0)
dp[a][j]=min(dp[a][j],dp[!a][j-s[i]]);
if(j+s[i]>=0)
dp[a][j]=min(dp[a][j],dp[!a][j+s[i]]+1);
}
a=!a;
}
if(dp[!a][sum/2]>sum/2)
printf("-1\n");
else
printf("%d\n",dp[!a][sum/2]);
}
return 0;
}