NYOJ-1170 最大的数

时间限制： 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、0时，就要用‘+’了，而且还要考虑清楚左加还是右加。

附上一组数据

12

1 1 1 1 1 1 1 1 1 1 1 1

81

在这组数据上栽了两次，NYOJ一次，写博客一次都忘了考虑了。

#include <stdio.h>int a[10005];int main(){ int n; while(~scanf("%d",&n)) { for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<n;i++){ if(a[i]==1){ int left=1,right=1; if(i==0){ while(a[i+right]==0) right++; a[i+right]++; } else if(i==n-1){ while(a[i-left]==0) left++; a[i-left]++; } else{ while(a[i+right]==0&&i+right<n) right++; while(a[i-left]==0&&i-left>=0) left++; if(i+right==n||a[i-left]==2)//想想为啥等于2 的时候可以直接加 a[i-left]++; else if(i-left<0||a[i+right]==2) a[i+right]++; else a[i+right]<a[i-left]?a[i+right]++:a[i-left]++; } a[i]=0; } } int max=1; for(int i=0;i<n;i++){ if(a[i]==0) continue; max *= a[i]; max %= 10086; } printf("%d\n",max); } return 0;}