首页 > 代码库 > 最大的数(nyoj 1170)

最大的数(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
来源
calamity_coming
上传者
ACM_孙毓阳
syy出的非常好的贪心题
思路是这样的 
遇到1就相加 (得考虑左边加还是右边加的情况,优先考虑左边)
1 1 1 1的情况
0 2 1 1
0 2 0 2  2*2=4
3 2 0 0 1//找到左边不为0的数+1
3 3 0 0 1
4 1 4 1//为什么要优先左边
 
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
using namespace std;
int a[10005];
void add(int l,int r)
{
    if(a[l]==2)
    {
        a[l]++;
        return ;
    }
    if(a[l]==0)
        l--;
    a[l]<=a[r]?a[l]++:a[r]++;
}
int main()
{
    int n;
    while(cin>>n)
    {
        int i,j;
        for(i=0; i<n; i++)
            cin>>a[i];
        if(a[0]==1)
        {
            a[1]++;
            a[0]=0;
        }
        for(i=1; i<n-1; i++)
            if(a[i]==1)
            {
                a[i]=0;
                add(i-1,i+1);//左加or右加
            }
        if(a[n-1]==1&&n>1)
        {
            for(i=n-2; !a[i]; i--);//0
            a[i]++;
            a[n-1]=0;
        }
        int sum;
        for(i=0,sum=1; i<n; i++)
            if(a[i])
                sum=(sum*a[i])%10086;
        cout<<sum<<endl;
    }
}
        


最大的数(nyoj 1170)