题解 | #小苯的ovo2.0#

ovo 的中间一定是个 v，那就别纠结整串，盯着每个 v 看它能配出多少组。

如果最后一共放了 k 个 o，当前前面已经有 j 个 o，那这个位置放 v 的贡献就直接是 j*(k-j)；所以做个 DP，边走边决定这位放 o 还是 v，把贡献最大化。

void solve(){
    string s;cin>>s;
    int n=(int)s.size();
    int c0=0,cq=0;
    for(int i=0;i<n;++i){
        if(s[i]=='o')++c0;
        else if(s[i]=='?')++cq;
    }
    ll ans=0;
    for(int i=c0;i<=c0+cq;++i){
        vvll dp(n+1,vll(i+1,-LINF));
        dp[0][0]=0;
        for(int j=1;j<=n;++j){
            char c=s[j-1];
            for(int k=0;k<=i;++k){
                if(c!='o'&&dp[j-1][k]!=-LINF){
                    dp[j][k]=max(dp[j][k],dp[j-1][k]+1LL*k*(i-k));
                }
                if(c!='v'&&k>0&&dp[j-1][k-1]!=-LINF){
                    dp[j][k]=max(dp[j][k],dp[j-1][k-1]);
                }
            }
        }
        ans=max(ans,dp[n][i]);
    }
    cout<<ans<<endl;
}