HDU-4651-连续最大积

缺乏、安全感 2022-04-25 04:18 164阅读 0赞

> 题目衔接：[http://acm.hdu.edu.cn/showproblem.php?pid=4561][http_acm.hdu.edu.cn_showproblem.php_pid_4561]

>  
> 
> # 连续最大积 #
> 
> **Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)  
> Total Submission(s): 3314    Accepted Submission(s): 955**  
>   
>  
> 
> **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看成一个挡板，统计每两个挡板之间的-2的个数与2的个数，如果-2的个数为偶数直接把两个数的个数相加即可，如果为奇数，就找到第一个-2和最后一个-2的位置，然后分别比较去掉这两个数后的长度，将每次的结果比较下即可。

但是我们还要先处理下，如果全是2或-2或2和-2的情况，我们就要给它在开头和结尾加上0就好了

代码：

/*
    题目大意:
    
    
    思路:用0做挡板，统计两个0之间2和-2的个数，如果-2为偶数直接输出两个数的和
    如果-2的个数为奇数，找到第一个-2的位置和最后一个-2的位置，比较去掉两者之一之后那个串更长
    
    */
    #include<map>
    #include<set>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include <vector>
    #include<cstring>
    #include<sstream>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll long long
    #define ul unsigned long long
    #define inf 0x3f3f3f
    #define esp 1e-8
    #define pp printf("\n");
    #define pn(a) printf("%d\n",a);
    #define bug printf("mmp\n");
    #define mm(a,b) memset(a,b,sizeof(a))
    #define T() int test,q=1;scanf("%d",&test); while(test--)
    const int maxn=2e4+10;
    const double pi=acos(-1.0);
    const int N=201;
    const int mod=1e9+7;
    int a[maxn];
    int chose(int st,int n)
    {
        int num1=0,num2=0,sts=0,ed=0;
        for(int i=st;i<=n;i++)
        {
           if(!a[i])
           {
               ed=i;
               break;
           }
           if(a[i]==2)
            num1++;
           if(a[i]==-2)
           {
              sts=i;
              break;
           }
        }
        if(sts==0&&ed)///从当前到结束全是正2
        {
            return ed-st;
        }
        int last=0;
        for(int i=sts;i<=n;i++)
        {
            if(a[i]==-2)
            {
                last=i;///更新最后一个-2的位置
                num2++;
            }
            else if(a[i]==0)
            {
                ed=i;///这里标记最后一个0的位置
                break;
            }
            else if(a[i]==2)
            {
                num1++;
            }
        }
        if(num2%2==0)///-2个数为偶数则直接输出即可
        {
            return (num1+num2);
        }
        else///如果是奇数个则比较第一个-2的位置和本次区域内最后一个-2的位置与结束位置的选取
        {
            int ans1=(ed-1)-sts;///去掉第一个-2
            int ans2=last-st;///去掉最后一个-2
            return max(ans1,ans2);
        }
    }
    int  main()
    {
        T()
        {
            mm(a,0);
            int n;
            scanf("%d",&n);
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
            }
            a[0]=0;
            a[n+1]=0;
            int ans=0;
            for(int i=0;i<n+1;i++)
            {
                if(a[i]==0)
                {
                    ans=max(ans,chose(i+1,n+1));
                }
            }
            printf("Case #%d: %d\n",q++,ans);
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_4561]: http://acm.hdu.edu.cn/showproblem.php?pid=4561