01串的代价-美团2023笔试(codefun2000)

题目链接
01串的代价-美团2023笔试(codefun2000)

题目内容

塔子哥有一个 01 串 s。每次操作可以将一个 1 修改为 0 或者一个 0 修改为 1 。塔子哥不喜欢 01 串相邻字符相等，所以他要操作使得 01 串任意相邻字符不相等。对于一个 01 串，其权值为使得相邻字符不相等的最少操作次数。
现在塔子哥想问你，对于给定的 s ，其所有子串的权值之和是多少。

输入描述

一行，一个 01 串 s(∣s∣≤2000) 。

输出描述

一个整数，表示一个 01 串的所有子串的权值之和是多少。

样例1

输入

000

输出

3

样例2

输入

011101

输出

11

样例解释

题解1

#include<bits/stdc++.h>
using namespace std;
const int N = 2005;

int n, ans, dp[N][2]; // dp[i][0/1]表示使区间[1,i]内相邻字符不相等的最少操作次数，并且第i位为0/1 
char s[N]; 

int main(){
	scanf("%s", s + 1);
	n = strlen(s + 1);
	for(int i = 1; i <= n; i++) {
		if(s[i] == '0'){
			dp[i][0] = dp[i - 1][1];
			dp[i][1] = dp[i - 1][0] + 1;
		} else {
			dp[i][0] = dp[i - 1][1] + 1;
			dp[i][1] = dp[i - 1][0];
		}
	}
	for(int i = 1; i < n; i++){
		for(int j = i + 1; j <= n; j++) {
			if((i%2) == (j%2)){  //区间[i,j]端点的奇偶性相同 
				ans += min(dp[j][0] - dp[i - 1][1], dp[j][1] - dp[i - 1][0]);
			}else {
				ans += min(dp[j][0] - dp[i - 1][0], dp[j][1] - dp[i - 1][1]);
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}