Gym - 100989 L / M 【dfs / dp】

题目链接：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代码：

 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 const int inf = 0x3f3f3f3f;

 using namespace std;

 int arr[], n;

 int ans = inf, flag = ;

 void dfs(int sum, int deep, int cnt)

 {

     if(deep == n - )

     {

         if(sum == )

         {

             flag = ;

             ans = min(ans, cnt);

         }

         return ;

     }

     dfs(sum + arr[deep + ], deep + , cnt); //不改变符号

     dfs(sum - arr[deep + ], deep + , cnt + ); //改变符号

     return ;

 }

 int main()

 {

     cin.sync_with_stdio(false);

     char ch;

     int x;

     cin >> n >> arr[];

     for(int i = ; i < n; i ++)

     {

         cin >> ch >> x;

         if(ch == '-')

             arr[i] = -x;

         else

             arr[i] = x;

     }

     dfs(arr[], , );

     if(flag)

         printf("%d\n", ans);

     else

         printf("-1\n");

 }

M代码：

 #include<iostream>

 #include<string.h>

 #include<algorithm>

 #define mem(a, b) memset(a, b, sizeof(a))

 const int MAXN =  *  + ;

 const int inf = 0x3f3f3f3f;

 using namespace std;

 int n, sum = ;

 int arr[];

 int dp[][MAXN]; //表示前i项的和为j时所改变的最少符号次数

 int main()

 {

     cin.sync_with_stdio(false);

     cin >> n;

     cin >> arr[];

     sum += arr[];

     for(int i = ; i <= n; i ++)

     {

         char ch;

         int x;

         cin >> ch >> x;

         sum += x;

         if(ch == '+')

             arr[i] = x;

         else

             arr[i] = -x;

     }

     if(sum % )  //绝对值的和为奇数的时候 不可能通过修改符号使得表达式的结果为0 例如, 1 1 1， 1 1 1 1 1

         printf("-1\n");

     else

     {

         mem(dp, inf);

         dp[][sum + arr[]] = ;

         for(int i = ; i <= n; i ++)

         {

             for(int j = ; j <=  * sum; j ++)//枚举和

             {

                 if(j >= arr[i])

                     dp[i][j] = min(dp[i][j], dp[i - ][j - arr[i]]);//满足可以不修改符号

                 if(j >= -arr[i])

                     dp[i][j] = min(dp[i][j], dp[i - ][j + arr[i]] + );//满足可以修改符号

             }

         }

         if(dp[n][sum] == inf)

             printf("-1\n");

         else

             printf("%d\n", dp[n][sum]);

     }

     return ;

 }

巴特西

Gym - 100989 L / M 【dfs / dp】

最新文章

热门文章