1 条题解

  • 0
    @ 2025-12-27 10:47:12
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+5;
    int a[maxn],b[maxn],dp[maxn],idx=0;
    
    void f(string s){
        int p;
        while(1){
            p=s.find("abc");
            if(p==-1) break;
            s=s.replace(p,3,"A");
        }
        //
        s+='.';
        int len=s.length(),c=0;
        for(int i=0;i<len;i++){
            if(s[i]=='A' && c==0) c=1;
            else if(s[i]=='A' && s[i-1]=='A') c++;
            else if(s[i]!='A' && s[i-1]=='A'){
                b[++idx]=c;
                c=1;
            }
        }
    }
    
    int g(int n){
        memset(dp,0,sizeof(dp));
        //
        dp[1]=a[1];
        for(int i=2;i<=n;i++){
            dp[i]=a[i];
            for(int j=1;j<=i/2;j++){
                dp[i]=max(dp[i],dp[j]+dp[i-j]);
            }
        }
        return dp[n];
    }
    
    
    int main(){
        int n,m,ans=0;
        string s;
        cin >> n;
        for(int i=1;i<=n;i++) cin >> a[i];
        //
        cin >> m >> s;
        //
        f(s);
        //
        for(int i=1;i<=idx;i++){
            if(b[i]==1) ans+=a[1];
            else ans+=g(b[i]);
        }
        cout << ans;
        //
        return 0;
    }
    

    计算得分(洛谷 P10721 普及/提高-)(GESP真题)(整数拆分问题)

    信息

    ID
    711
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    11
    已通过
    3
    上传者