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取余

样例输入

样例输出

9

15

找到1，让一的作用最大化

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int a[10010];

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(scanf("%d",&n)!=EOF)

	{

		int i,j;

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

			scanf("%d",&a[i]);

		if(a[1]==1)

		{

			a[2]++;

			a[1]=0;

		}

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

		{

			if(a[i]==1)

			{

				a[i]=0;

				add(i-1,i+1);

			}

		}

		if(a[n]==1&&n>1)

		{

			for(i=n-1;!a[i];i--);

			a[i]++;

			a[n]=0;

		}

		int sum;

		for(i=1,sum=1;i<=n;i++)

		{

			if(a[i])

				sum=(sum*a[i])%10086;

		}

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

	}

	return 0;

}

巴特西

nyoj--1170--最大的数（数学技巧）

最大的数

最新文章

热门文章