Gym

题目链接：http://codeforces.com/gym/100989/problem/L / http://codeforces.com/gym/100989/problem/M

题目大意：给定一个具有N项的表达式，求出最少修改符号次数使得表达式的和为0.

题目分析：

1.两道题的题意一模一样，区别在于数据范围不同。L题N的范围在20以内，但是表达式中每一项的值范围在 1e9 之内。M题的N范围在300之内，每一项的值范围在300之内。

2.所以L题用枚举，枚举每一种修改的情况取最少修改次数。M题无法枚举，但由于值的范围在300以内，表达式的和值的范围为 [-90000, +90000].所以用运用dp。

3.枚举用dfs即可。dp[i][j]表示前i项和为j时符号最少修改次数。下标不能为负,所以下标加上N项绝对值的和sum。使得 0 的意义是原本的 - sum, 2 * sum的意义是原本sum, sum的意义是原本的 0。那么dp[n][sum]就是我们所求的答案。

L代码：

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 const int inf = 0x3f3f3f3f;
 5 using namespace std;
 6 
 7 int arr[50], n;
 8 int ans = inf, flag = 0;
 9 
10 void dfs(int sum, int deep, int cnt)
11 {
12     if(deep == n - 1)
13     {
14         if(sum == 0)
15         {
16             flag = 1;
17             ans = min(ans, cnt);
18         }
19         return ;
20     }
21     dfs(sum + arr[deep + 1], deep + 1, cnt); //不改变符号
22     dfs(sum - arr[deep + 1], deep + 1, cnt + 1); //改变符号
23     return ;
24 }
25 
26 int main()
27 {
28     cin.sync_with_stdio(false);
29     char ch;
30     int x;
31     cin >> n >> arr[0];
32     for(int i = 1; i < n; i ++)
33     {
34         cin >> ch >> x;
35         if(ch == '-')
36             arr[i] = -x;
37         else
38             arr[i] = x;
39     }
40     dfs(arr[0], 0, 0);
41     if(flag)
42         printf("%d
", ans);
43     else
44         printf("-1
");
45 }

M代码：

 1 #include<iostream>
 2 #include<string.h>
 3 #include<algorithm>
 4 #define mem(a, b) memset(a, b, sizeof(a))
 5 const int MAXN = 90000 * 2 + 10;
 6 const int inf = 0x3f3f3f3f;
 7 using namespace std;
 8 
 9 int n, sum = 0;
10 int arr[350];
11 int dp[350][MAXN]; //表示前i项的和为j时所改变的最少符号次数
12 
13 int main()
14 {
15     cin.sync_with_stdio(false);
16     cin >> n;
17     cin >> arr[1];
18     sum += arr[1];
19     for(int i = 2; i <= n; i ++)
20     {
21         char ch;
22         int x;
23         cin >> ch >> x;
24         sum += x;
25         if(ch == '+')
26             arr[i] = x;
27         else
28             arr[i] = -x;
29     }
30     if(sum % 2)  //绝对值的和为奇数的时候 不可能通过修改符号使得表达式的结果为0 例如, 1 1 1， 1 1 1 1 1 
31         printf("-1
");
32     else
33     {
34         mem(dp, inf);
35         dp[1][sum + arr[1]] = 0;
36         for(int i = 2; i <= n; i ++)
37         {
38             for(int j = 0; j <= 2 * sum; j ++)//枚举和 
39             {
40                 if(j >= arr[i])
41                     dp[i][j] = min(dp[i][j], dp[i - 1][j - arr[i]]);//满足可以不修改符号 
42                 if(j >= -arr[i])
43                     dp[i][j] = min(dp[i][j], dp[i - 1][j + arr[i]] + 1);//满足可以修改符号 
44             }
45         }
46         if(dp[n][sum] == inf)
47             printf("-1
");
48         else
49             printf("%d
", dp[n][sum]);
50     }
51     return 0;
52 }