题目
俄罗斯套娃是一些尺寸递增的木制雕像，它们可以嵌套在一起。每个套娃可以放进一个更大的套娃，也可以被放入一个更小的套娃。每个套娃内部最多只能直接嵌套一个套娃，但是那个套娃内部还可以继续嵌套。 给定n个尺寸互不相同的套娃，按尺寸从小到大依次编号为1到n。如果套娃a被直接嵌入套娃b，那么我们称b是a的父亲，如果一个套娃没有父亲，那么我们称它是自由的。一组镶嵌方案可以用每个套娃的父亲来表示。
我们可以每步可以做以下两种操作中的任意一种： 1.把一个自由的套娃直接嵌入一个更大的没有被放入东西的套娃。 2.选择一个不自由的套娃，将其从其父亲中取出。
给定初始局面，请计算达到目标局面的最小的操作步数。
题解
乱搞 这样想，最复杂的步数为2*n（拆开+装上）。 什么情况下可以省步数呢？当这个套娃及其里面的套娃都不会拿出来的时候里面的套娃就可以完全不用操作。 如果一个套娃原来就是自由的，或者最后是自由的，那么它也可以减少操作。
小结
从最坏情况考虑，减去可以优化的步数，是一个套路。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=100010;
int n,ans;
int a[MAXN],b[MAXN];bool tail[MAXN];
int main()
{
scanf("%d",&n);ans=0;
for(int i=1;i<=n;i++) scanf("%d",&a[i]),tail[a[i]]=true;
for(int i=1;i<=n;i++) scanf("%d",&b[i]),tail[b[i]]=true;
for(int i=1;i<=n;i++)
{
if(a[i]) ans++;
if(b[i]) ans++;
if(!tail[i])
{
int x=i;
while(a[x] && b[x] && a[x]==b[x])
{
ans-=2;x=a[x];
}
}
}
printf("%d\n",ans);
return 0;
}
