箱包网站建设策划报告,app开发学习网站,如果网站设计时,网站模板下载地址【卡码网】31. 字符串的最大价值
给定一个字符串 S S S#xff08;S.lenth 5000#xff09;#xff0c;只包含 0 和 1 两个数字#xff0c;下标从 1 开始#xff0c;设第 i i i 位的价值为 v a l i val_i vali#xff0c;则 v a l i val_i vali的定义如下S.lenth 5000只包含 0 和 1 两个数字下标从 1 开始设第 i i i 位的价值为 v a l i val_i vali则 v a l i val_i vali的定义如下
当 i 1 时 v a l 1 val_1 val1 1 当 i 1 时 若 S i S_i Si ! S ( i − 1 ) S_{(i - 1)} S(i−1) v a l i val_i vali 1 若 S i S_i Si S ( i − 1 ) S_{(i - 1)} S(i−1) v a l i val_i vali v a l ( i − 1 ) val_{(i - 1)} val(i−1) 1
字符串 S 的总价值等于 val1 val2 … valnn为字符串 S 的长度。你可以任意删除字符串 S 中的任意字符使得字符串 S 的总价值能够达到最大。
输入 输入只有一行为字符串 S 输出 输出一个整数代表答案
样例输入
010101样例输出
7提示 删除一些字符后S变为 0001 或 0111 时能够达到最大价值。
题解
v v 1的递增效果肯定要比 v 1 强很多尽可能制造 v v 1 的情况找出所有 0 和 1 的个数, 让数量多的一方连成块, 这里得出来的值构成了答案的中间部分再加上俩边的不同字符。
这个方案的核心思想是通过计算不同部分连续字符对最终价值的贡献来得到最大的价值。
核心思路
首先使用 count 数组来记录字符 ‘0’ 和 ‘1’ 的个数。对于每个字符 ‘0’ 和 ‘1’都分别计算以其为分界的情况下的价值。对于以字符 ‘0’ 为分界的情况
找到第一个字符 ‘0’ 出现的位置 start 和最后一个字符 ‘0’ 出现的位置 end。计算连续字符 ‘0’ 所对应的价值(1 count[c - ‘0’]) * count[c - ‘0’] / 2其中 count[c - ‘0’] 是字符 ‘0’ 的个数。也就是将 ‘0’ 之间的所有 ‘1’ 逻辑上删除。计算字符 ‘0’ 之前连续字符 ‘1’ 所对应的价值(1 start) * start / 2。计算字符 ‘0’ 之后连续字符 ‘1’ 所对应的价值(s.length() - end) * (s.length() - end - 1L) / 2这里要注意长度减1。
同样的对于以字符 ‘1’ 为分界的情况重复上述步骤。最后从这两种情况中选择较大的一个作为最终的最大价值。
import java.lang.*;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);String s in.nextLine();// count 数组来记录字符 0 和 1 的个数int[] count new int[2];for (char c : s.toCharArray()) {count[c - 0];}//对于每个字符 0 和 1都分别计算以其为分界的情况下的价值long result Math.max(getValue(0, s, count), getValue(1, s, count));System.out.println(result);}public static long getValue(char c, String s, int[] count) {//找到第一个字符 0 出现的位置 start 和最后一个字符 0 出现的位置 end。int start s.indexOf(c);int end s.lastIndexOf(c);System.out.println(start: start\nend: end);System.out.println(s.length(): s.length());//计算连续字符 0 所对应的价值(1 count[c - 0]) * count[c - 0] / 2其中 count[c - 0] 是字符 0 的个数。也就是将 0 之间的所有 ‘1’ 逻辑上删除。long num (1L count[c - 0]) * count[c - 0] / 2;//计算字符 0 之前连续字符 1 所对应的价值(1 start) * start / 2。num (1L start) * start / 2;//计算字符 0 之后连续字符 1 所对应的价值(s.length() - end) * (s.length() - end - 1L) / 2这里要注意长度减1。num (s.length() - end) * (s.length() - end - 1L) / 2;return num;}
}
