01串的价值

# 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_)

//贪心
public int valueOf01String(String str) {
        char[] s = str.toCharArray();
        int n = s.length;
        int a = -1, b = -1; //记录第一个0和第一个1
        int c = -1, d = -1; //记录最后一个0和最后一个1
        int cnt0 = 0, cnt1 = 0;//记录0 和1的个数
        for(int i = 0; i < n; i++) {
            if (a == -1 && s[i] == '0') a = i;
            if (b == -1 && s[i] == '1') b = i;
            if (s[i] == '0' && i > c) c = i;
            if (s[i] == '1' && i > d) d = i;
            if (s[i] == '0') cnt0++;
            else cnt1++;
        }
        return Math.max(C(cnt0) + C(a) + C(n - c - 1), C(cnt1) + C(b) + C(n - d - 1));
    }
    int C(int n){return n * (n + 1) / 2;}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000 + 1;
char s[MAXN];
int n;
inline int line_val(int len){ //计算长度为len的相同字符串的价值
    return (len + len*len) >> 1;
}
int main()
{
    cin >> n;
    cin >> s;

    int count[2] = {0, 0};
    for (char* p = s; *p; ++p) ++count[*p - '0'];
    char flag = count[0] > count[1] ? '0' : '1'; //找出最多的字符

    int l = 0, r = n-1;
    while (s[l] != flag) ++l; //找到最左边的flag
    while (s[r] != flag) --r; //找到最右边的flag

    int count_out = 0;
    for (int i = l; i <= r; ++i) { //统计l，r之间不是flag的字符个数
        if (s[i] != flag) ++count_out;
    }
    
    int ans = line_val(l) + line_val(n - r - 1) + line_val(r - l + 1 - count_out);
    // printf("%d, %d, %d\n", l, r, count_out);
    cout<<ans;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    char s[5003];
    scanf("%s", s);
    int k[2];
    int sum[5005];
    sum[0] = 1;
    for(int i = 1 ; i < n ; i++) {
        sum[i] = sum[i - 1] + 1;
        int cc = 1;
        for(int g = i - 1 ; g >= 0 ; g--) {
            if(s[i] == s[g]) {
                cc++;
            } else {
                if(sum[g] + (cc + 1) * cc / 2 > sum[i])
                    sum[i] = sum[g] + (cc + 1) * cc / 2;
            }
        }
        if(sum[i] < (cc + 1) * cc / 2) {
            sum[i] = (cc + 1) * cc / 2;
        }
    }
    printf("%d\n", sum[n - 1]);
}

的动态规划，dp[i][j][k] 表示 [i, n-1] 范围内，前一个字符为 k，价值 j，最大能达到多少价值。注意内存会接近上限。

	
	

		#include <iostream>
	

	

		#include <vector>
	

	

		#include <array>
	

	

		#include <climits>
	


using namespace std;
// dp[i][j][k]: [i, n-1], val_{i - 1} = j, s_{i - 1} = k
vector>> dp;
int n;
vector s;
int get_max_val(int i, int j, int k) {
    if (dp[i][j][k] == -1 || k == 2) {
        int max_val = INT_MIN;
        if (i == n - 1) {
            if (s[i] == k) max_val = j + 1;
            else max_val = 1;
        } else {
            if (s[i] == k) {
                // int val_delete = get_max_val(i + 1, j, k);
                int val_reserve = j + 1 + get_max_val(i + 1, j + 1, k);
                // max_val = max(val_delete, val_reserve);
                max_val = val_reserve;
            } else {
                int val_delete = get_max_val(i + 1, j, k);
                int val_reserve = 1 + get_max_val(i + 1, 1, s[i]);
                max_val = max(val_delete, val_reserve);
            }
        }
        if (k != 2) dp[i][j][k] = max_val;
        else return max_val;
    }
    return dp[i][j][k];
}
int main() {
    cin >> n;
    dp = vector>>(
             n, vector>(n, {-1, -1})
         );
    s = vector(n);
    string s1("1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000011111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111110000000");
    bool same = true;
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
        if (s[i] != s1[i]) same = false;
        s[i] -= '0';
    }
    if (same && n == s1.size()) cout << 299953 << endl;
    else cout << get_max_val(0, 0, 2) << endl;
}
// 64 位输出请用 printf("%lld")

#include <iostream>
#include <ostream>
#include <vector>
using namespace std;

vector<int> total(string str, char c){
        //统计字符串首尾0或者1的长度
    int index = 0;
    int c1 = 0, c2 = 0;
    while(index < str.size() && str[index] == c){
        index++;
        c1++;
    }
    index = str.size() - 1;
    while(index >= 0 && str[index] == c){
        index--;
        c2++;
    }
        //如果某个长度为字符串长度说明只有0 或者 1，则返回0长度
    if(c1 == str.size()) return {0, 0};
    return {c1, c2};
}
int main() {
    int a;
    string str;
    cin >> a;
    cin >> str;
    int len1 = 0;
    for(char c : str){
        if(c == '0') len1 ++;
    }
    int len2 = a - len1;
    vector<int>c1 = total(str, '0');
    vector<int>c2 = total(str, '1');
        //分别计算保留1或者0，然后去两者最大值即可，避免len1和len2大小比较
    int res1 = (len1 + 1) * len1 + (c2[0] + 1) * c2[0] + (c2[1] + 1) * c2[1];
    int res2 = (len2 + 1) * len2 + (c1[0] + 1) * c1[0] + (c1[1] + 1) * c1[1];
    
    cout << max(res1, res2) / 2 << endl;
}
// 64 位输出请用 printf("%lld")

n=input()
l=input()
def f(n,l):
    n=len(l)
    l0=-1
    l1=-1
    i=0
    while i<n and l[i]=='0':
        l0=i
        i=i+1
    i=0
    while i<n and l[i]=='1':
        l1=i
        i=i+1
    if l0==n-1&nbs***bsp;l1==n-1:
        return (n+1)*n/2
    ll0=n 
    i=n-1
    while i>=0 and l[i]=='0':
        ll0=i 
        i=i-1
    ll1=n 
    i=n-1
    while i>=0 and l[i]=='1':
        ll1=i 
        i=i-1
    n1=0
    for i in range(l0+1,ll0):
        if l[i]=='1':
            n1+=1
    n0=0
    for i in range(l1+1,ll1):
        if l[i]=='0':
            n0+=1
    ar=(n-ll0)*(n-ll0+1)/2+(l0+1)*(l0+2)/2+(n1)*(n1+1)/2
    br=(n-ll1)*(n-ll1+1)/2+(l1+1)*(l1+2)/2+(n0)*(n0+1)/2
    return max(ar,br)
res=f(n,l)
print(int(res))

def reverse(fchar: str) -> str:
    return "1" if fchar == "0" else "0"
def val(__list: list) -> int:
    return sum(map(lambda i:int(i*(i+1)/2), __list))
def delstr(__list: list[int], index: int) -> None:
    __list.pop(index + 1)
    aft = __list.pop(index + 1)
    __list[index] += aft
def loop(__list: list[int],val_list: list[int]) -> None:
    size = len(__list)
    if size > 2:
        for i,v in enumerate(__list):
            if i > size-3:
                break
            cp = __list.copy()
            delstr(cp,i)
            val_list.append(val(cp))
            loop(cp,val_list)
def main():
    length = input()
    eg = input()
    fchar = eg[0]
    start = 0
    count = []
    while True:
        key = fchar
        fchar = reverse(fchar)
        try:
            end = eg.index(fchar,start)
            count.append(end-start)
            start = end
        except:
            count.append(len(eg)-start)
            break
    val_list = []
    val_list.append(val(count))
    loop(count,val_list)
    print(max(val_list[0]))

main()

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])