WA2求助测试样例
查看原帖
WA2求助测试样例
567554
carnation13楼主2022/4/2 10:01

自己想的DPDP做法,想知道哪个测试样例没过

代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,a[200005],f[200005][2];
signed main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        ll x=0,xb;
        cin>>n;
        memset(a,0,sizeof(a));
        for(ll i=1;i<=n;++i)cin>>a[i];
        memset(f,-1,sizeof(f));
        ll now=1,ma=0;
        while(now<=n&&a[now]==0)++now;
        if(a[now]==2)f[now][1]=1;
        if(a[now]==-2)f[now][0]=1;
        if(a[now]==1)f[now][1]=0;
        if(a[now]==-1)f[now][0]=0;
        ma=max(ma,f[now][1]);
        if(now==n+1){cout<<n<<" "<<0<<endl;continue;}
        for(ll i=now+1;i<=n;++i)
        {
            if(a[i]==1)
            {
                if(f[i-1][1]>=0)f[i][1]=f[i-1][1];
                if(f[i-1][0]>=0)f[i][0]=f[i-1][0];
            }
            if(a[i]==2)
            {
                if(f[i-1][1]>=0)f[i][1]=f[i-1][1]+1;
                if(f[i-1][0]>=0) f[i][0]=f[i-1][0]+1;
                f[i][1]=max(f[i][1],1ll);
            }
            if(a[i]==-1)
            {
                if(f[i-1][1]>=0)f[i][0]=f[i-1][1];
                if(f[i-1][0]>=0)f[i][1]=f[i-1][0];
            }
            if(a[i]==-2)
            {
                if(f[i-1][1]>=0)f[i][0]=f[i-1][1]+1;
                if(f[i-1][0]>=0)f[i][1]=f[i-1][0]+1;
                f[i][0]=max(f[i][0],1ll);
            }
            if(a[i]==0)
            {
                while(i<=n&&a[i]==0)++i;
                if(i==n+1)break;
                if(a[i]==2)f[i][1]=1;
                if(a[i]==-2)f[i][0]=1;
                if(a[i]==1)f[i][1]=0;
                if(a[i]==-1)f[i][0]=0;
                --i;
            }
            ma=max(ma,f[i][1]);
        }
        for(ll i=1;i<=n;++i)
        {
            if(f[i][1]==ma)
            {
                xb=i;
                break;
            }
        }
        ll w=0,fu=0;
        for(ll i=xb;i>=1;--i)
        {
            if(a[i]<0)++fu;
            if(abs(a[i])==2)++w;
            if(w==ma&&fu%2==0)
            {
                x=i-1;
                break;
            }
        }
        if(ma==0)cout<<n<<" "<<0<<endl;
        else
        cout<<x<<" "<<n-xb<<endl;
    }
    return 0;
}
2022/4/2 10:01
加载中...