hdu4561 连续最大积

题意:

连续最大积

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)

Total Submission(s): 1354 Accepted Submission(s): 458

Problem Description

小明和他的好朋友小西在玩一个游戏，由电脑随机生成一个由-2，0，2三个数组成的数组，并且约定，谁先算出这个数组中某一段连续元素的积的最大值，就算谁赢！

比如我们有如下随机数组：

2 2 0 -2 0 2 2 -2 -2 0

在这个数组的众多连续子序列中，2 2 -2 -2这个连续子序列的积为最大。

现在小明请你帮忙算出这个最大值。

Input

第一行输入一个正整数T，表示总共有T组数据(T <= 200)。

接下来的T组数据，每组数据第一行输入N，表示数组的元素总个数（1<= N <= 10000）。

再接下来输入N个由0，-2，2组成的元素，元素之间用空格分开。

Output

对于每组数据，先输出Case数。

如果最终的答案小于等于0，直接输出0

否则若答案是2^x ，输出x即可。

每组数据占一行，具体输出格式参见样例。

Sample Input

2

2

-2 0

10

2 2 0 -2 0 2 2 -2 -2 0

Sample Output

Case #1: 0

Case #2: 4

思路:

和最大连续子序列差不多,当0的时候置为0,要注意的事还有开个东西,记录当前有多少个负数,更新的时候只有偶数的时候在更新,就这样,果断敲完,果断wa了,哎! 其实没考虑到这个问题,-2 2 2 2 2 2 我们在倒着跑一便就能排除这种情况了,因为毕竟只有奇偶两种情况...还有一点就是,如果最小的是-2那么只哟一种情况就是只哟一个数字并且这个数字是-2,自己稍微想下就明白,不解释...

#include<stdio.h>

#define N (10000 + 500)



int num[N];

int main ()

{

   int t ,n ,i ,ans_max ,cas = 1;

   scanf("%d" ,&t);

   while(t--)

   {

      scanf("%d" ,&n);

      int mk0 = 0;

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

      {

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

         if(num[i]) mk0 = 1;

      }

      printf("Case #%d: " ,cas ++);

      if(!mk0 || n == 1 && num[1] == -2)

      {

         printf("0\n");

         continue;

      }

      ans_max = 0;

      int now = 0;

      int ss = 0;

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

      {

         if(!num[i])

         {

            ss = now = 0;

            continue;

         }

         if(num[i] < 0) ss ++;

         now ++;

         if(ss % 2 == 0 && ans_max < now)

         ans_max = now;

      }

      now = 0;

      ss = 0;

      for(i = n ;i >= 1;i --)

      {

         if(!num[i])

         {

            ss = now = 0;

            continue;

         }

         if(num[i] < 0) ss ++;

         now ++;

         if(ss % 2 == 0 && ans_max < now)

         ans_max = now;

      }

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

   }

   return 0;

}

巴特西

hdu4561 连续最大积

最新文章

热门文章