前缀和

问题： 第一题 问题描述 小A的门前有n个排成一排的栅栏，编号分别为1,2，...，n。每个栅栏都是红色或者蓝色的。但小A觉得目前的上色方案看起来有些杂乱，便想要重新对栅栏进行涂色。具体地，小A认为，如果栅栏的颜色交替次数多于1次，那么就是杂乱的，否则就是整齐的。换言之，如果栅栏是全红/全蓝/前一段红后一段蓝/前一段蓝后一段红，那么都能符合小A的要求。请问小A至少需要对几个栅栏进行重新涂色，才能满足他的要求呢？ 输入描述 第一行是一个整数n，表示有n个栅栏，1<=n<=100000。 第二行是一个字符串s，字符串只包含’r’和’b’，对于第i个字符，若为’r’表示第i个栅栏为红色，...

#include <iostream> #include <vector> using namespace std; int main() { //读取数据 int n,q; cin >> n >>q; vector<int> arr(n +1); for(int i = 1; i <= n; i++) cin >> arr[i]; //预处理前缀和数组 vector<long long> dp(n + 1); for(int i = 1; i <= n; i++) dp[i] = dp[i - 1...