自己想的DP做法,想知道哪个测试样例没过
代码如下
#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;
}