Description
https://www.luogu.com.cn/problem/P6820
Solution
很好的 dp 题目啊。
首先贪心感觉不能做到全局最优，考虑 dp。
令 $f_{i,j}$ 表示匹配到 $i,j$ 的最小花费。有：
$f_{i,j}\gets\min (f_{i-1,j},f_{i,j-1})+1$
$f_{i,j}\gets\min(f_{i-1,j-1})+1,a_i\not = b_j$。
显然如果能用下面转移是不劣的。而上面转移的次数是 $O(n)$ 的，考虑从这个角度优化。
把两维的 dp 看成在矩形上，对于 $a_i=b_j$ 的格点我们成为特殊点。对于一个，如果反对角线没有其他特殊点那么 $f_{i,j}=\max(i,j)$，否则就从反对角线的上一个特殊点斜着转移过来。
对于非特殊点我们不用去管；对于特殊点 $(i,j)$，我们快速找到 $(i-1,j)$ 和 $(i,j-1)$ 的值，然后取最小。
最后查询 $(n,n)$ 的值即可。
复杂度 $O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
int sum=1;
while (y) {
if (y&1) sum=sum*x%mod;
x=x*x%mod;y>>=1;
}
return sum;
}
int n,a[maxn],b[maxn],ans,vis[maxn],f[maxn];
pair<int,int> g[maxn*2];
int calc(int x,int y) {
if (g[x-y+n].fi==0) return max(x,y);
return -g[x-y+n].fi+x+g[x-y+n].se;
}
signed main(void){
int l,r,i;
read(n);
for (i=1;i<=n;i++) read(a[i]);
for (i=1;i<=n;i++) read(b[i]),vis[b[i]]=i;
for (i=1;i<=n;i++) {
f[i]=min(calc(i-1,vis[a[i]]),calc(i,vis[a[i]]-1))+1;
g[i-vis[a[i]]+n]=mk(i,f[i]);
}
printf("%d\n",calc(n,n));
return 0;
}
|