最大的数---贪心算法

1023: 最大的数

时间限制: 1000 Sec   内存限制: 128 MB 提交: 14   解决: 4 [ 提交][ 状态][ 讨论版]

题目描述

小明和小红在打赌说自己数学学的好，于是小花就给他们出题了，考考他们谁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在两边时1 2 3肯定是右加1  ；3 2 1左加1

而1在中间时按照贪心的策略：尽量保证当前的数达到最大值，比较左加1和右加1的值越接近越好 与较小的相加！！

如：1 2 1 3  第二个1 前面1+2=3  当前左边值为3 右边值为3 相同择左右均可 结果：（1+2+1）*3=12

1 1 2 1 1  --> (1+1）*（2+1+1）=8

3 1 5 --》（3+1）*5=20

#include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int n; int i,a[10005],sum; while(scanf("%d",&n)!=EOF){ for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0,sum=1;i<n;i++){ if(a[i]==1) {a[i+1]+=1;} else if(a[i]!=1&&a[i+1]==1&&(a[i]<a[i+2]||i+1==n-1)) {a[i+1]=a[i]+1;}// 左值小于右的 --左加1 else if(a[i]!=1&&a[i+1]==1&&a[i]>=a[i+2]) {sum=(sum*a[i])086; a[i+2]+=1;i++;}//左边大于右边 --右加1 else {sum=(sum*a[i])086; }//一般处理 } printf("%d\n",sum086);//!!!!每一步乘的结果都要对10086取余 } //system("PAUSE"); return 0; }

注意：大数据的处理mod10086 在运算过程中都要取余！！！