学步园

思路：
一串数，例如 0 0 0 1 1 0 0 1 1 0 0 0 1 1 1，截取每一段类似1 1 0 0的一段，算出一个Bi，Bi的话，是使这一段1 1 0 0的f(A, B)最小，可以通过求导得到，如给的例子是 1 1 0 0 和 1 1 0 0 0。然后，比较Bi和Bi-1。如果前者小于后者，那么Bi和Bi-1的这两段应该合并为一段计算。可以不管串首的连续的0和串尾的连续的1。

比较Bi和Bi-1时，每一次合并都要检查一次栈顶。

AC代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#define eps 1e-8

using namespace std;

const int maxn = 1e5+10;
int num[maxn];
long long zo[maxn][2];

int main()
{
    int T;
    scanf("%d", &T);
    for(int cas = 0; cas < T; cas++)
    {
        int n;
        scanf("%d", &n);
        int zero = 0;
        int one = 0;
        bool flag1 = false; /// 记录是否全部为1
        bool flag0 = false; /// 记录是否全部为0
        bool flag2 = true; /// 记录是否只有串首连续0和串尾连续1
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &num[i]);
            if(num[i] == 1) one++;
            else zero++;
        }
        if(zero == 0) flag1= true;
        if(one == 0) flag0 = true;
        double sum = 0;
        if(!flag0 && !flag1)
        {
                long long cnt1 = 0;
                long long cnt0 = 0;
                int k = 0; ///栈顶指针
                memset(zo, 0, sizeof(zo));
                for(int i = 0; i < n; i++)
                {
                        if(num[i] == 1) cnt1++;
                        if(num[i] == 0) cnt0++;
                        /// 记录每一个1 1 0 0串中1和0的个数，当连续的0为串首时忽略
                        if(cnt0 && cnt1 == 0) cnt0 = 0;
                        /// 当扫到1 1 0 0串扫到下一个串开头或是整个串结尾时
                        if(cnt1 && cnt0 && (i == n-1 || num[i+1] == 1))
                        {
                                flag2 = false;
                                zo[k][1] = cnt1;
                                zo[k][0] = cnt0;
                                cnt1 = cnt0 = 0;
                                ///检查栈顶
                                while(k > 0 && zo[k-1][1]*(zo[k][1]+zo[k][0]) >= zo[k][1]*(zo[k-1][0]+zo[k-1][1]))
                                {
                                        zo[k-1][1] += zo[k][1];
                                        zo[k-1][0] += zo[k][0];
                                        zo[k][1] = zo[k][0] = 0;
                                        k--;
                                }
                                k++;
                        }
                }
                for(int i = 0; i < k; i++)
                {
                        double Bi = (double)zo[i][1] / (double)(zo[i][0]+zo[i][1]);
                        sum += (double)zo[i][1]*(1-Bi)*(1-Bi) + (double)zo[i][0]*Bi*Bi;
                }
        }
        if(flag1 || flag0 || flag2) printf("0.000000\n");
        else printf("%.6lf\n", sum);
    }
}