9.2 OPPO笔试 后端（B卷）

前两题打卡

第一题注意”最多操作1次“，可以不操作，否则只能过70%

第三题动态规划，dp[i][j]表示为以str[i]为最后一个”oppo“右端点的情况下，有j个”oppo“字串

分两种情况，如果以str[i-3]为第j-1个字串的右端点，则最后一个字串是”ppo“；其余情况最后一个字串是”oppo“

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        in.nextLine();
        String str = in.nextLine();
        if (str.length() < 4 + (k-1)*3){
            System.out.println(-1);
            return;
        }
        int[][] dp = new int[str.length() + 1][k + 1];
        //避免计算，直接存最小值
        int[][] minn = new int[str.length() + 1][k + 1];
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i],0x7ffffff0);
            Arrays.fill(minn[i],0x7ffffff0);
        }
        for (int i = 0; i <= str.length(); i++) {
            dp[i][0] = 0;
            minn[i][0] = 0;
        }
        for (int i = 1; i <= str.length(); i++) {
            for (int j = 1; j <=k ; j++) {
                int targetLen = 4 + (j-1)*3;
                if (i < targetLen){
                    dp[i][j] = 0x7ffffff0;
                    continue;
                }
                //长度满足
                if (j == 1){
                    //o p  p   o
                    //    i-1  i
                    int opNum = 0;
                    if (str.charAt(i-1) != 'o') opNum++;
                    if (str.charAt(i-2) != 'p') opNum++;
                    if (str.charAt(i-3) != 'p') opNum++;
                    if (str.charAt(i-4) != 'o') opNum++;
                    dp[i][j] = dp[i-4][j-1] + opNum;
                    minn[i][j] = Math.min(minn[i-1][j],dp[i][j]);
                } else {
                    // p p o 情况
                    int opNum = 0;
                    if (str.charAt(i-1) != 'o') opNum++;
                    if (str.charAt(i-2) != 'p') opNum++;
                    if (str.charAt(i-3) != 'p') opNum++;
                    dp[i][j] = dp[i-3][j-1] + opNum;
                    if (str.charAt(i-4) != 'o') opNum++;
                    dp[i][j] = Math.min(minn[i-4][j-1] + + opNum,dp[i][j]);
//                    for (int l = 4; l <= i-4 ; l++) {
//                        dp[i][j] = Math.min(dp[l][j-1] + opNum,dp[i][j]);
//                    }
                    minn[i][j] = Math.min(minn[i-1][j],dp[i][j]);
                }
            }
        }
        int res = 0x7fffffff;
        for (int i = 4 + (k-1)*3; i <= str.length() ; i++) {
            res = Math.min(res,dp[i][k]);
        }
        System.out.println(res);
    }

`