2 条题解

  • 0
    @ 2025-10-8 17:10:16
    #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
      @ 2025-10-8 17:09:58
      #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
      上传者