P6820 [PA2012]Two Cakes DP状态优化

题意：

戳这里

分析：

很久以前做过的题，在巨佬 fgf 的帮助下又学了一遍

暴力

直接设 DP 状态 (f[i][j]) 表示第一个序列枚举到第 (i) 位，第二个序列枚举到第 (j) 位时的最短时间，按题意模拟就好了

正解

我们发现暴力做法中大部分的情况下 DP 都没有做出任何决策直接转移了，所以有好多状态是无用的。所以我们只考虑 (a[x]==b[y]) 这种特殊状态下的 DP，对于其他的情况直接转移向 (a[x]==b[y]) 的情况

当 (a[x]==b[y]) 时

f[x]=min(dfs(x-1,y),dfs(x,y-1))+1;

因为一个 (x) 一定只会对应一个 (y) ,所以这种情况只会遇到一次，那么直接对于 (x) 记忆化就可以了，之后遇到直接返回值就可以了

当 (a[x]!=b[y]) 时

我们需要找到之前他们刚好相等时的另一个点，我们注意到当转移是不会影响两个点的差值，所以我们直接对于每一类差值，存一下它们下一次相同时的点的位置，然后直接二分的查找

复杂度 (O(n log n)) , 因为决策点只有 (n) 个，每一次不同的情况都会 (O(log n)) 的跳

代码：

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define lc rt<<1
#define rc rt<<1|1
#define pb push_back
#define fir first
#define sec second

using namespace std;

namespace zzc
{
	inline int read()
	{
		int x=0,f=1;char ch=getchar();
		while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
		while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
		return x*f;
	}
	
	const int maxn = 1e6+5;
	int a[maxn],b[maxn],pos[maxn],f[maxn];
	int n;
	vector<int> del[maxn<<1];
	
	int get(int id,int pos)
	{
		int l=0,r=del[id].size()-1,mid,res=0;
		while(l<=r)
		{
			mid=(l+r)>>1;
			if(del[id][mid]<=pos)
			{
				res=del[id][mid];
				l=mid+1;
			}
			else r=mid-1;
		}
		return res;
	}
	
	int dfs(int x,int y)
	{
		if(!x||!y) return x|y;
		if(a[x]==b[y])
		{
			if(!f[x]) f[x]=min(dfs(x-1,y),dfs(x,y-1))+1;
			return f[x]; 
		}
		int pre=get(x-y+n,x);
		return pre?dfs(pre,y+pre-x)+(x-pre):max(x,y);
	}
	
	void work()
	{
		n=read();
		for(int i=1;i<=n;i++) a[i]=read();
		for(int i=1;i<=n;i++)
		{
			b[i]=read();
			pos[b[i]]=i;
		}
		for(int i=1;i<=n;i++) del[i-pos[a[i]]+n].pb(i);
		printf("%d
",dfs(n,n));
	}

}

int main()
{
	zzc::work();
	return 0;
}