Educational Codeforces Round 153 (Rated for Div. 2) D. Balanced String(基础dp)

题目

长为s(3<=|s|<=100)的01串，

每次操作，可以交换两个位置的数字，

求最小的操作次数，使得串平衡（串中01子序列的个数等于10子序列的个数）

题目保证串合法，即一定可以换到平衡态

思路来源

官方题解&洛谷

题解

01交换：可以看成是一次0翻转1操作+一次1翻转0操作，从而消除了后效性

dp[i][j][k]：只考虑前i个字符，总共有j个0，子序列中有k个01子序列时的最小翻转次数

即把0翻成1 或者 把1翻成0

枚举第i个字符翻不翻

则最终交换的次数=保证0的个数还是原来的情况下，(把0翻成1的次数+把1翻成0的次数)/2

注意，交换操作不改变00和11的数量

所以，最终01子序列=10子序列=二者之和的一半=cnt0*cnt1/2

注意到cnt0*cnt1为奇数时无解，但题目已经保证输入合法

代码

#include
// #include
// #include
// #include
// #include
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define dbg(x) cerr<<(#x)<<":"<" ";
#define dbg2(x) cerr<<(#x)<<":"<
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pb push_back
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
//std::mt19937_64 gen(std::chrono::system_clock::now().time_since_epoch().count());
//ll get(ll l, ll r) { std::uniform_int_distribution dist(l, r); return dist(gen); }
const int N=105,INF=0x3f3f3f3f;
int n,dp[2][N][N*N],cnt0,cnt1;
char s[N];
void upd(int &x,int y){
    x=min(x,y);
}
int main(){
    scanf("%s",s);
    n=strlen(s);
    memset(dp,INF,sizeof dp);
    dp[0][0][0]=0;
    rep(i,0,n-1){
        int v=s[i]-'0',cur=i&1,nex=cur^1;
        memset(dp[nex],INF,sizeof dp[nex]);
        cnt0+=(v==0);
        rep(j,0,n){
            rep(k,0,n*n){
                if(dp[cur][j][k]==INF)continue;
                rep(l,0,1){
                    upd(dp[nex][j+(l==0)][k+j*(l==1)],dp[cur][j][k]+(v!=l));
                }
            }
        }
    }
    cnt1=n-cnt0;
    printf("%d\n",dp[n&1][cnt0][cnt0*cnt1/2]/2);
	return 0;
}