题解 | 小苯的ovo2.0

import java.util.*;

public class Main{
    static Scanner in = new Scanner(System.in);
    static final int inf = -0x3f3f3f3f;
    static void solve(){
        String s = in.nextLine();
        //System.out.println(s.length());
        int cnto = 0;
        int cntq = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == 'o') cnto ++;
            if(s.charAt(i) == '?') cntq ++;
        }
        long[][] f = new long[s.length() + 5][s.length() + 5];
        long ans = 0;
        int n = s.length();
        for(int i = cnto; i <= cnto + cntq; i++){
            for(int j=0;j<=n;j++)
                for(int k=0;k<=i;k++)
                    f[j][k] = inf;
            f[0][0] = 0;
            for(int j = 1; j <= n; j++){
               for(int k = 0;k <= i;k++){
                    if(s.charAt(j-1) != 'o' && f[j-1][k] != inf){
                        f[j][k] = Math.max(f[j][k], f[j-1][k] + (long)(i-k)*k);
                    }
                    if(s.charAt(j-1) != 'v' && k > 0 && f[j-1][k-1] != inf){
                        f[j][k] = Math.max(f[j][k], f[j-1][k-1]);
                    }
               }
            }
            ans = Math.max(ans, f[n][i]);
        }
        System.out.println(ans);
    }
    public static void main(String[] args){
        int T = in.nextInt();
        String ss = in.nextLine();
        while(T-- > 0) solve();
    }
}