首先，设\(1\)有\(c_1\)个，\(0\)有\(c_0\)个
\(01\)串中数字间只有四种关系，分别是\(00\)，\(01\)，\(10\)，\(11\)
不难发现，第一种和第四种的数量是固定的，为$ \frac { c_0 \times ( c_0 - 1 ) }{2} $ 和 $ \frac {c_1 \times ( c_1 - 1 )}{2}$
同时，另外两种加起来一共有\(c_1 \times c_0\)种
然后以\(1\)为例，容易得出
\[所有1的前面的数字个数的总和\ -\ 11对出现的次数=01对出现的次数
\]
即
\[\sum_{i=1}^n[s_i=1]-\frac {c_1 \times ( c_1 - 1 )}{2}=\frac{c_1 \times c_0}{2}
\]
同理
\[\sum_{i=1}^n[s_i=1]-\frac {c_1 \times ( c_1 - 1 )}{2}=\frac{c_1 \times c_0}{2}
\]
设\(dp_{i,j,k}\)为前\(i\)个放\(j\)个\(0\)，\(0\)的下标\(-1\)的和为\(k\)的最小逆转次数
答案即为\(dp_{n,c_0,\frac{c_1 \times c_0}{2}}\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
char s[105];
int a[105];
int dp[105][55][5005];
void solve(){
scanf("%s",s+1);
int n=strlen(s+1),c1=0,c0;
for(int i=1;i<=n;i++)
a[i]=s[i]-'0';
for(int i=1;i<=n;i++)
c1+=a[i];
c0=n-c1;
if(c1<c0){
for(int i=1;i<=n;i++)
a[i]^=1;
swap(c1,c0);
}
int s1,s0;
s1=(n*(n-1)/2+c1*(c1-1)/2-c0*(c0-1)/2)/2;
s0=n*(n-1)/2-s1;
for(int i=0;i<=n;i++)
for(int j=0;j<=c0;j++)
for(int k=0;k<=s0;k++)
dp[i][j][k]=1e9;
dp[0][0][0]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<=min(c0,i);j++)
for(int k=0;k<=s0;k++){
if(j&&k>=i-1)dp[i][j][k]=min(dp[i][j][k],dp[i-1][j-1][k-(i-1)]+a[i]);
dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]+(a[i]^1));
}
printf("%d\n",dp[n][c0][s0]/2);
}
int main(){
int t=1;
//scanf("%d",&t);
while(t--)solve();
return 0;
}