Hdu 4561 连续最大积 (dp或暴力)

绝地灬酷狼 2022-09-21 01:28 126阅读 0赞

整理过去的代码时发现的题，收藏了一份写得不错的代码，已经不记得是参考了谁的了。。。

第一份是别人写的，稍微修改了一下，出处不记得了。。。。

第二份是当年比赛时自己写的，好搓。。。。

#include <cstdio>
    #include <cstdlib>
    
    int data[10005];
    
    typedef struct{
        int val,sig;
    }Mul;
    Mul operator*(const Mul& x,const int& y){
        Mul res=x;
        switch(y){
            case 2:res.val++;break;
            case 0:res.val=res.sig=0;break;
            case -2:res.val++;res.sig=-res.sig;break;
        }
        return res;
    }
    Mul fmax(Mul a,Mul b){
        if (a.sig==b.sig)
            if(a.sig>=0)return a.val>=b.val?a:b;
            else return a.val<=b.val?a:b;
        else
            return a.sig>b.sig?a:b;
    }
    Mul fmin(Mul a,Mul b){
        if(a.sig==b.sig)
            if(a.sig>=0)return a.val<=b.val?a:b;
            else return a.val>=b.val?a:b;
        else
            return a.sig<b.sig?a:b;
    }
    
    int main ()
    {
        int T;
        scanf("%d",&T);
        for (int Cas=1;Cas<=T;Cas++)
        {
            int n,i;
            Mul max,min,tmp,tmax,ans;
            scanf("%d",&n);
            for (i=0;i<n;i++)
                scanf("%d",&data[i]);
            max.val=abs(data[0])/2;
            max.sig=(data[0]==0?0:data[0]/2);
            ans=min=max;
            for (i=1;i<n;i++)
            {
                tmp.val=abs(data[i])/2;
                tmp.sig=(data[i]==0?0:data[i]/2);
                tmax=max;
                max=fmax(tmp,fmax(max*data[i],min*data[i]));
                min=fmin(tmp,fmin(min*data[i],tmax*data[i]));
                ans=fmax(max,ans);
            }
            if (ans.sig<=0)
                ans.val=0;
            printf("Case #%d: %d\n",Cas,ans.val);
        }
        return 0;
    }

#include <cstdio>
    #include <iostream>
    #include <queue>
    #include <cstring>
    #include <string>
    #include <algorithm>
    using namespace std;
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    
    
    int data[10005];
    
    int main ()
    {  
    #ifdef ONLINE_JUDGE
    #else
        freopen("1010.in","r",stdin);
    	freopen("1010.out","w",stdout);
    #endif
        int T;
        scanf("%d",&T);
        for (int Cas=1;Cas<=T;Cas++)
        {
            printf("Case #%d: ",Cas);
            memset(data,0,sizeof(data));
            int n,i,mm=-100000;
            scanf("%d",&n);
            for (i=0;i<n;i++)
            {
                scanf("%d",&data[i]);
            }
            n++;
            for (i=0;i<n;i++)
            {    
                if (data[i]!=0)
                {
                    int j;
                    int z=0,f=0;
                    for (j=i;j<n && data[j];j++)
                    {
                        if (data[j]<0)
                            f++;
                        else
                            z++;
                    }
                    int rr=j-1;  //i~rr
                    if (f%2==0)//偶数
                        mm=max(mm,f+z);
                    else
                    {
                        int k,zuo=0,you=0;
                        for (k=i;k<=rr;k++)
                        {
                            zuo++;
                            if (data[k]<0)
                                break;                            
                        }
                        for (k=rr;k>=i;k--)
                        {
                            you++;
                            if (data[k]<0)
                                break;                            
                        }
                        int temp=min(zuo,you);
        //                printf("%d %d %d %d\n",zuo,you,i,temp);
                        mm=max(mm,rr-i+1-temp);
                    }
                }
                else
                    mm=max(0,mm);
            }
            printf("%d\n",mm);
        }
        return 0;
    }