题解 | DNA序列,动态规划

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // gc长度用dp,相减
    // 比例
    string s;cin>>s;
    int n;cin>>n;
    vector<int>dp(s.size(),0);
    int ratio=0;
    string s2;
    if(s[0]=='G'||s[0]=='C')dp[0]=1;
    for(int i=1;i<s.size();i++){
        if(s[i]=='G'||s[i]=='C')dp[i]=dp[i-1]+1;
        else dp[i]=dp[i-1];
        if(i>=n-1){
            if((dp[i]-dp[i-n])>ratio){
                s2=s.substr(i-n+1,n);
                ratio=dp[i]-dp[i-n];
            }
        }
    }
    cout<<s2<<endl;
    if(n>s.size())cout<<s<<endl;

}
// 64 位输出请用 printf("%lld")

一开始想用双指针，后来发现子串长度是固定的，那直接-n不就完了吗？比例也不用算，n是固定的。直接动态规划计数，然后比较。唯一问题是substr用的比例有点高，其实可以多用一个int 储存i的，最后再substr，才想起来，懒得改了。