P12346[蓝桥杯 2025 省A 第二场]基因配对 动态规划做法

· · 题解

思路

可以用动态规划做。

我们设传进来的字符串为 a。

状态：f_{i,j} 表示在字符串中两个分别以 a_i 和 a_j 开头的两个子串能匹配（指能使得 a_{i\ldots i+f_{i,j}} 与 a_{j\ldots j+f_{i,j}} 互反）的最大长度。

状态转移方程：当 a_i 与 a_j 不等时即是 f_{i+1,j+1}+1（也就是在 a_i、a_j 之后一个数 a_i+1、a_j+1 开头能最大匹配的长度加 1），否则就是没有匹配，即为零。

AC CODE

#include<iostream>
#include<queue>
#include<utility>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<string>
#include<climits>
#include<vector>
namespace noip {
    using Int=long long;
    constexpr Int Max_N=1000;
    char a[1+Max_N];
    Int f[1+Max_N][1+Max_N]{};
    void init(){}
    void main(){
        std::cin>>a;Int n=std::strlen(a);
        for(Int i=n;i--;){
            for(Int j=n;j--;){
                f[i][j]=a[j]!=a[i]?1+f[i+1][j+1]:0;
            }
        }
        Int ans=0;
        for(Int i=0;i<n;i++){
            for(Int j=i+1;j<n;j++){
                ans+=std::min(j-i,f[i][j]);//防止计算的两个子串重叠,因为题目要求 b 小于 c 
            }
        }
        std::cout<<ans<<std::endl;
    }
}
int main(){
    noip::init();
    noip::main();
    return 0;
}