首页 > 试题广场 >

01串的价值

[编程题]01串的价值
  • 热度指数：3199 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给出一个只包含 0 和 1 的 01 串 s ，下标从 1 开始，设第 i 位的价值为 vali ，则价值定义如下：

1. i=1时:val1 = 1
2. i>1时：
2.1 若 si ≠ si-1 , vali = 1
2.2 若 si = si-1 , vali = vali-1 + 1
字符串的价值等于 val1 + val2 + val3 + ... + valn

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

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


输出描述:
输出一个整数代表答案
示例1

输入

6
010101

输出

7

说明

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

输入

20
11111000111011101100

输出

94
示例3

输入

4
1100

输出

6
算法知识视频讲解
添加回答
Python
珞珈山苏灿头像 珞珈山苏灿
分享一个思路，不一定正确，但通过了全部的测试。最大的结果一定是连续串。举个例子00101111，最大的串一定是0011111。这启发我们结果串一定具有这样的结构AAAABBB之类的，有可能全A或者全B。因此只需思考可能出现的连续串的情况，一共有两种可能的结构。1，全一样，例AAAAA。2，AAABBBBB.。但A和B有0、1两种选择。分析之后一共有5中情况。
1.原串全是同一个字符，此时原串最大。
2.左边连续的字符+剩余最多的字符。例如000111111
3.右边连续的字符+剩余最多的字符。例如00000111
但左边连续和右边连续的字符可能是同一字符，例如0000*****000这样的结构。
此时最长串结构有两种情况。
4。丢掉中间的所有与两边连续一致的字符，所有字符为左右连续字符，例如0000000。
5。保留中间所有与两边连续不一致的字符，丢掉一致的。即00001111···11000。

一共上面5种可能。核心是让同一字符连续最多次。即AAAA...AABBBB...BB这样的结构，有可能全A,全B，也有可能都有，最终一定是以上结构里的最大值。
细节见代码。 
n=int(input())
s=input()
vals=[1]*n
cnt1=0
v0=1
for i in range(1,n):
    if s[i]=='1':
        cnt1+=1
    if s[i]==s[i-1]:
        vals[i]=vals[i-1]+1
    v0+=vals[i]
if s[0]=='1':
    cnt1+=1
cnt0=n-cnt1

left_char=s[0]
left_c=1
right_char=s[-1]
right_c=1
for i in range(1,n):
    if s[i]!=s[i-1]:
        break
    left_c+=1
for i in range(n-2,-1,-1):
    if s[i]!=s[i+1]:
        break
    right_c+=1

mp={0:cnt0,1:cnt1}
v1=left_c*(left_c+1)//2+mp[1-int(left_char)]*(mp[1-int(left_char)]+1)//2
v2=right_c*(right_c+1)//2+mp[1-int(right_char)]*(mp[1-int(right_char)]+1)//2
v3=1
v4=1

if left_char==right_char:
    v3=left_c*(left_c+1)//2+right_c*(right_c+1)//2+mp[1-int(left_char)]*(mp[1-int(left_char)]+1)//2
    v4=mp[int(left_char)]*(mp[int(left_char)]+1)//2
if max(cnt0,cnt1)==n:
    print(v0)
else:
    print(max(v0,v1,v2,v3,v4))
    
        


发表于 2024-04-05 00:20:46 回复(0)
Python
给了offer就去赶海头像 给了offer就去赶海
测试用例肯定有问题 
思路：压缩+动态规划 
import sys

def solution():
    def f(num):
        return (1+num)*num // 2
    n = int(input())
    s = input()

    count = 1
    res = 0
    nums = []
    for i in range(len(s)):
        if i > 0:
            if s[i] == s[i-1]:
                count += 1
            else:
                nums.append(count)
                count = 1
    nums.append(count)
    # print(nums)
    m = len(nums)
    dp = [[0,0] for _ in range(m)]
    dp[0][0] = nums[0]
    dp[0][1] = f(dp[0][0])
    if m <= 1:
        return dp[-1][-1]
    dp[1][0] = nums[1]
    dp[1][1] = f(dp[0][0]) + f(dp[1][0])

    for i in range(2,m):
        dp[i][0] = dp[i-2][0] + nums[i]
        if i % 2 == 1:
            dp[i][1] = max(dp[i][1],f(dp[i][0])+dp[0][1])
        else:
            dp[i][1] = max(dp[i][1], f(dp[i][0]))
        # dp[i][1] = max(dp[i][1],f(dp[i][0]))
        for j in range(i-2,-1,-2):
            # print(f'(i,j):{i,j} val:{f(dp[i][0] - dp[j][0]) + dp[j+1][1]}')
            dp[i][1] = max(f(dp[i][0] - dp[j][0]) + dp[j+1][1],dp[i][1])
        # print()
    # print(dp)
    return dp[-1][-1]
if __name__ == "__main__":
    print(solution())


发表于 2023-09-11 21:55:03 回复(0)
Python
牛客160600003号头像 牛客160600003号
import sys
n = input()
s = input()
s_list = list(s)
i = 1
count_o = 0
count_l = 0
count_s = 0
count_e = 0
a = 0
b = 0
key_num = 0
aaaaa = 0
for num in s_list:
if int(num) == 0:
count_o += 1
 else:
count_l += 1
 i += 1

if count_o < count_l:
a = count_l
b = 1
else:
a = count_o
for num in s_list:
if int(num) != b:
count_s += 1
 if int(num) == b:
break
s_list_r = reversed(s_list)
for num in s_list_r:
if int(num) != b:
count_e += 1
 if int(num) == b:
break
key_num = (a+1)*a/2 + (count_s+1)*count_s/2 + (count_e+1)*count_e/2
aaaaa = int(key_num)
print(aaaaa)
发表于 2023-08-20 16:05:52 回复(1)
Python
臆想者头像 臆想者 
# 45ms 4700KB  所有测试样例全A!
from collections import defaultdict
n = int(input())
s = input()
zero_len = s.count("0")
one_len = s.count("1")
temp_dict = defaultdict(int)
if zero_len>one_len:
    temp_dict["left"] = len(s[0:s.index("0")])
    temp_dict["right"] = len(s[n-s[::-1].index("0"):])
    temp_dict["max"] = zero_len
elif one_len>zero_len:
    temp_dict["left"] = len(s[0:s.index("1")])
    temp_dict["right"] = len(s[n-s[::-1].index("1"):])
    temp_dict["max"] = one_len
elif one_len==zero_len:
    temp_dict["max"] = one_len
    if len(s[0:s.index("0")])+len(s[n-s[::-1].index("0"):])>=len(s[0:s.index("1")])+len(s[n-s[::-1].index("1"):]):
        temp_dict["left"] = len(s[0:s.index("0")])
        temp_dict["right"] = len(s[n-s[::-1].index("0"):])
    else:
        temp_dict["left"] = len(s[0:s.index("1")])
        temp_dict["right"] = len(s[n-s[::-1].index("1"):])
sum_ = 0
for i in temp_dict:
    cur_val = 1
    for j in range(temp_dict[i]):
        sum_+=cur_val
        cur_val+=1
print(sum_)

发表于 2022-07-25 22:32:29 回复(1)
Python
Ultron201911031047310头像 Ultron201911031047310 
leng = int(input().strip())
string = list(map(int, input().strip()))
vals = [0] * leng
vals[0] = 1
for i in range(1, leng):
    vals[i] = vals[i - 1] + 1
    cc = 1
    j = i - 1
    while j >= 0:
        if string[i] == string[j]:
            cc +=1
        else:
            temp = vals[j] + (cc + 1) * cc / 2
            if temp > vals[i]:
                vals[i] = temp
        j -= 1
    temp = (cc + 1) * cc / 2

    if temp > vals[i]:
        vals[i] = temp

print(vals[leng - 1])

编辑于 2022-05-19 21:21:30 回复(1)
提交观点

问题信息

上传者：小小
难度：
5条回答 9545浏览

热门推荐

通过挑战的用户

相关试题

01串的价值

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号