网站模板资源,营销培训机构哪家最专业,网页制作培训班课程,保险官网题目
长为s(3|s|100)的01串#xff0c;
每次操作#xff0c;可以交换两个位置的数字#xff0c;
求最小的操作次数#xff0c;使得串平衡#xff08;串中01子序列的个数等于10子序列的个数#xff09;
题目保证串合法#xff0c;即一定可以换到平衡态
思路…题目
长为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为奇数时无解但题目已经保证输入合法
代码
#includebits/stdc.h
// #includeiostream
// #includevector
// #includequeue
// #includemap
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 pairint,int P;
#define fi first
#define se second
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#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_distributionll dist(l, r); return dist(gen); }
const int N105,INF0x3f3f3f3f;
int n,dp[2][N][N*N],cnt0,cnt1;
char s[N];
void upd(int x,int y){xmin(x,y);
}
int main(){scanf(%s,s);nstrlen(s);memset(dp,INF,sizeof dp);dp[0][0][0]0;rep(i,0,n-1){int vs[i]-0,curi1,nexcur^1;memset(dp[nex],INF,sizeof dp[nex]);cnt0(v0);rep(j,0,n){rep(k,0,n*n){if(dp[cur][j][k]INF)continue;rep(l,0,1){upd(dp[nex][j(l0)][kj*(l1)],dp[cur][j][k](v!l));}}}}cnt1n-cnt0;printf(%d\n,dp[n1][cnt0][cnt0*cnt1/2]/2);return 0;
}
