一升菌 level
获赞
70
粉丝
1
关注
20
看过 TA
396
门头沟学院
2025
Java
IP属地:湖北
暂未填写个人简介
私信
关注
09-06 17:16
门头沟学院 Java
看解答都是三维dp好像二维dp也能做dp[i][j]表示子串s[i...j]全变为1的最小操作数public static void main(String[] args) {        Scanner in = new Scanner(System.in);        int n = in.nextInt();        String s = in.next();        char[] cs = s.toCharArray();        int res = 0;        int[][] dp = new int[n][n];        for(int i = 0; i             dp[i][i] = cs[i] == '0' ? 1 : 0;            res += cs[i] == '0' ? 1 : 0;        } for (int i = n - 1; i >= 0; i--) {            for(int j = i + 1; j                 if(cs[j] == '1'){                    dp[i][j] = dp[i][j - 1];                }else{                    if(cs[j - 1] == '0'){                        dp[i][j] = dp[i][j - 1];                    }else{                        dp[i][j] = dp[i][j - 1] + 2;                    }                }                if((j - i + 1) % 2 != 0 && dp[i][j] % 2 != 0){                    res ++;                }            }        }        System.out.println(res);    }
查看3道真题和解析 投递携程等公司10个岗位
0 点赞 评论 收藏
分享
关注他的用户也关注了:
牛客网
牛客企业服务