2 条题解
-
0
#include<bits/stdc++.h> using namespace std; int a[3005]; int b[3005]; int c[3005]; int dp1[3005][3005]; int dp2[3005][3005]; int aa[3005]; int bb[3005]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } int m; cin>>m; for(int i=1;i<=m;i++){ cin>>b[i]; } int k; cin>>k; for(int i=1;i<=k;i++){ cin>>c[i]; } // 计算a[1..i]与b[1..j]的LCS for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1]); if(a[i]==b[j]){ dp1[i][j]=max(dp1[i][j],dp1[i-1][j-1]+1); } } } // 计算a[i..n]与b[j..m]的LCS(反向) for(int i=n;i>=1;i--){ for(int j=m;j>=1;j--){ dp2[i][j]=max(dp2[i+!][j],dp2[i][j+1]); if(a[i]==b[j]){ dp2[i][j]=max(dp2[i][j],dp2[i+1][j+1]+1); } } } // 处理a中从i开始能否匹配c的全部k个元素 for(int i=1;i<=n;i++){ int cnt=1; aa[i]=i-1; while(cnt<=k && aa[i]<n){ aa[i]++; if(a[aa[i]]==c[cnt]){ cnt++; } } if(cnt<=k){ aa[i]=-1; } } // 处理b中从i开始能否匹配c的全部k个元素 for(int i=1;i<=m;i++){ int cnt=1; bb[i]=i-1; while(cnt<=k && bb[i]<m){ bb[i]++; if(b[bb[i]]==c[cnt]){ cnt++; } } if(cnt<=k){ bb[i]=-1; } } int ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(aa[i]!=-1 && bb[j]!=-1){ ans=max(ans,k+dp1[i-1][j-1]+dp2[aa[i]+1][bb[j]+1]); } } } if(ans==0){ cout<<-1; return 0; } cout<<ans; return 0; } -
0
#include<bits/stdc++.h> using namespace std; int a[3005]; int b[3005]; int c[3005]; int dp1[3005][3005]; int dp2[3005][3005]; int aa[3005]; int bb[3005]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } int m; cin>>m; for(int i=1;i<=m;i++){ cin>>b[i]; } int k; cin>>k; for(int i=1;i<=k;i++){ cin>>c[i]; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1]); if(a[i]==b[j]){ dp1[i][j]=max(dp1[i][j],dp1[i-1][j-1]+1); } } } for(int i=n;i>=1;i--){ for(int j=n;j>=1;j--){ dp2[i][j]=max(dp2[i+1][j],dp2[i][j+1]); if(a[i]==b[j]){ dp2[i][j]=max(dp2[i][j],dp2[i+1][j+1]+1); } } } for(int i=1;i<=n;i++){ int cnt=1; aa[i]=i-1; while(cnt<=k && aa[i]<n){ aa[i]++; if(a[aa[i]]==c[cnt]){ cnt++; } } if(cnt<=k){ aa[i]=-1; } } for(int i=1;i<=m;i++){ int cnt=1; bb[i]=i-1; while(cnt<=k && bb[i]<m){ bb[i]++; if(b[bb[i]]==c[cnt]){ cnt++; } } if(cnt<=k){ bb[i]=-1; } } int ans; ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(aa[i]!=-1 && bb[j]!=-1){ ans=max(ans,k+dp1[i-1][j-1]+dp2[aa[i]+1][bb[j]+1]); } } } if(ans==0){ cout<<-1; return 0; } cout<<ans; return 0; }
- 1
信息
- ID
- 5940
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者