南阳OJ 1170 最大的数

以你之姓@ 2023-10-06 09:42 23阅读 0赞

### 最大的数 ###

时间限制： 1000 ms | 内存限制：65535 KB

难度： 3

描述

小明和小红在打赌说自己数学学的好，于是小花就给他们出题了，考考他们谁NB，题目是这样的给你N个数

在这n个数之间添加N-1个\*或+，使结果最大，但不可以打乱原顺序，请得出这个结果

如

1 3 5

结果是（1+3）\*5=20；最大

可以添加若干个括号，但一定要保证配对，但是每两个数之间只可能有一个\*或+

数列最前和最后不应有+或乘

小明想赢小红但是他比较笨，请你帮帮他

输入

多组测试数据以EOF结束，每组有一个n（n<10000），然后有n个正整数a\[i\]（1<=a\[i\]<=20）

输出

输出最大的结果由于结果比较大，结果对10086取余

样例输入

3
    1 2 3
    3
    5 1 2

样例输出

9
    15

**题目解析：**

**　　本道题其实就是就是找 1，并分情况处理 1，考虑将其加到它的前边某个数上或它的下一个数上。**

示例代码：

1 #include<stdio.h>
     2 #include<string.h>
     3 using namespace std;
     4 
     5 #define MAX_NUM 10001
     6 
     7 int num[MAX_NUM];     //保存输入的数 
     8 int mark[MAX_NUM];    //标记，当不需要计算时，置-1 
     9 
    10 int main()
    11 {
    12     int n;
    13     while (scanf("%d", &n) != EOF)
    14     {
    15         for (int i = 0; i < n; i++)
    16             scanf("%d", &num[i]);
    17         memset(mark, 0, sizeof(num));
    18         
    19         if (num[0] == 1)      //如果第一个数为1 
    20         {
    21             num[1] += 1;      //则将它加到第二个数上 
    22             mark[0] = -1;     //将标记置-1，计算时就不需要算它 
    23         }
    24         if (num[n-1] == 1)    //如果最后一个数为1 
    25         {
    26             num[n-2] += 1;    //那么将它加到倒数倒数第二个数上 
    27             mark[n-1] = -1;
    28         }
    29         
    30         int tmp;
    31         for (int i = 1;i < n-1; i++)    //中间的数 
    32         {
    33             if (num[i] == 1)      //如果找到第i个数为1 
    34             {
    35                 mark[i] = -1;     //先将标记置-1 
    36                 tmp = i-1;        //先准备将它加到它前一个数上 
    37                 
    38                 while(mark[tmp] == -1) {    //如果它的前一个为1，且已经处理过了 
    39                     tmp--;                    //那么继续往前找 
    40                 }
    41                 
    42                 if (num[tmp] <= num[i+1] || num[tmp] == 2)    //利用贪心思想考虑将这个1加到它的前边还是后边 
    43                     //（1）如果找到它的前边那个不为1的数，且小于等于它的下一个数 或 
    44                     //（2）它的前边那个不为1的数为2，则加到前边那个不为1的数上边
    45                     num[tmp]++;
    46                 else//否则加到它的下一个数上 
    47                     num[i+1]++;
    48             }
    49         }
    50         
    51         int ans = 1;
    52         for (int i = 0; i < n; i++)
    53         {
    54             if (mark[i] != -1)    //将标记数组中不为-1的数相乘即为最大的数 
    55                ans = ans * (num[i]) % 10086;
    56         }
    57         printf("%d\n", ans);
    58     }
    59     
    60 }