```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int n,cnt=1,flag;
char c[2000000];
int z1[1005],a[1005],z2[1005];
void dfs(int z1c,int z2c,int numn,int numc,int ans)
{
if(ans==n+1)
{
flag=1;
for(int i=1;i<=numc;i++)
{
cout<<c[i]<<" ";
}
exit(0);
}
if(ans==a[numn])
{
c[numc]='a';
c[numc+1]='b';
dfs(z1c,z2c,numn+1,numc+2,ans+1);
return;
}
if(ans==z1[z1c])
{
c[numc]='b';
dfs(z1c-1,z2c,numn,numc+1,ans+1);
return;
}
if(ans==z2[z2c])
{
c[numc]='d';
dfs(z1c,z2c-1,numn,numc+1,ans+1);
return;
}
if(a[numn]<z1[z1c]||z1c==0)
{
z1[z1c+1]=a[numn];
c[numc]='a';
dfs(z1c+1,z2c,numn+1,numc+1,ans);
}
if(a[numn]<z2[z2c]||z2c==0)
{
z2[z2c+1]=a[numn];
c[numc]='c';
dfs(z1c,z2c+1,numn+1,numc+1,ans);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
dfs(0,0,1,1,1);
if(flag==0)
cout<<0;
return 0;
}
```
by 绫小路帆波 @ 2019-09-26 06:07:43
为了方便大佬看,我给一下我代码的基本思路
by 绫小路帆波 @ 2019-09-26 06:08:04
z1c指第一个栈指向的位置,z2c指第二个栈指向的位置,numn指a【n】数组指向的位置,numc指答案输出数组指向的位置,ans指现在指向了第几大的数,对于一个数字,进行递推,分别放入第一个栈和第二个栈,剪枝也写了,感觉随机数据比n2还要小很多,但是我只得了30分???为啥连n<=50都没过啊
by 绫小路帆波 @ 2019-09-26 06:12:01
错的点,全是tle,感觉生活失去了希望
by 绫小路帆波 @ 2019-09-26 06:12:39
您指望搜索复杂度具体到N^2……?
by _MRCMRC_ @ 2019-09-26 06:40:03
不要写$n^2$的,打个二分图染色加栈就可以了。
by 爱喝敌敌畏 @ 2019-09-26 07:19:14
代码我就没细看,感觉楼上正解
by 爱喝敌敌畏 @ 2019-09-26 07:19:39
同意楼上
by Sophon @ 2019-09-26 07:20:33