题目链接:https://codeforces.com/problemset/problem/489/B
动态规划解法:思路和LCS一致
#include<bits/stdc++.h> using namespace std; const int maxn=110; int a[maxn]; int b[maxn]; int dp[maxn][maxn]; int n,m; void solve(){ sort(a+1,a+1+n); sort(b+1,b+1+m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(abs(a[i]-b[j])==1 || a[i]==b[j]){ dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1); }else{ dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i][j-1])); } } } printf("%d",dp[n][m]); return ; } void INPUT(){ scanf("%d",&n); for(int i=1;i<=n;i++){ cin>>a[i]; } scanf("%d",&m); for(int i=1;i<=m;i++){ cin>>b[i]; } } int main() { INPUT(); solve(); return 0; }
双指针解法:
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; int a[maxn]; int b[maxn]; bool vis[maxn]; bool vis2[maxn]; double ans; int n,m; void solve(){ int cnt=0; int j=0; sort(a,a+n); sort(b,b+m); int l=0,r=0; while(l<n&&r<m){ if(abs(a[l]-b[r])==1||a[l]==b[r]){ l++; r++; cnt++; continue; } if(a[l]<b[r]-1){ l++; }else{ r++; } } printf("%d",cnt); return ; } void INPUT(){ scanf("%d",&n); for(int i=0;i<n;i++){ cin>>a[i]; } scanf("%d",&m); for(int i=0;i<m;i++){ cin>>b[i]; } } int main() { INPUT(); solve(); return 0; }