01串的价值

[编程题]01串的价值

热度指数：3199 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个只包含 0 和 1 的 01 串 s ，下标从 1 开始，设第 i 位的价值为 val_i ，则价值定义如下：

1. i=1时:val₁ = 1

2. i>1时：

2.1 若 si ≠ si-1 , val_i = 1

2.2 若 si = si-1 , val_i = val_i-1 + 1

字符串的价值等于 val₁ + val₂ + val₃ + ... + val_n

你可以删除 s 的任意个字符，问这个串的最大价值是多少。

输入描述:

第一行一个正整数 n ，代表串长度。
接下来一行一个 01 串 s 。
1 ≤ n ≤ 5,000

输出描述:

输出一个整数代表答案

示例1

输入

6
010101

输出

说明

删除后的串为0001或0111时有最大价值

示例2

输入

20
11111000111011101100

输出

示例3

输入

4
1100

输出

算法知识视频讲解

文和906

发表于 2022-05-05 14:45:13

动态规划解法。使用val数组来记录前i个元素的最大价值。初始化val[0]=1。从第二项开始遍历字符串。对每一项，其价值最小为上一项价值+1，如221。所以先将其价值预设为最小值，val[i]=val[i-1]+1。并设置一个计数，cnt=1。从i-1项开始，从后向前遍历字符串。当遇到与i 展开全文

ezis

发表于 2023-08-17 20:16:48

其实目前题解区的大部分网友们写的这种贪心算法是错误的，只能得出局部最优解，无法保证其正确性，只是本题测试用例有问题，才能AC罢了。错误的算法：因为以题目要求，1或0越聚集，以贪心的思想，想办法把0或1聚集起来，删除孤立的0或1，分成0占据了主导地位和1占据了主导地位的两种情况。对于这两种情况分展开全文