南宁比优建站,郑州短视频拍摄公司,浏览器官网,福州网站建设网络公司原题链接#xff1a;Problem - D - Codeforces 题面#xff1a; 大概意思就是让你在翻转01串不超过k次的情况下#xff0c;使得a*#xff08;0的最大连续长度#xff09;#xff08;1的最大连续长度#xff09;最大#xff08;1an#xff09;。输出n个数Problem - D - Codeforces 题面 大概意思就是让你在翻转01串不超过k次的情况下使得a*0的最大连续长度1的最大连续长度最大1an。输出n个数第i个数代表ai时的最大值。 思路可以发现n3000我们可以用O(n^2)的复杂度来求解。首先我们先假设最长连续0串在左边最长的连续1串在右边一开始最朴素的思想就是
枚举最长0串的左端点l和右端点r并且使它合法。设区间[l,r]中1的个数为x也就是说[l,r]变成全0串需要的操作数为x。然后O(n^2)求出区间[r1,n]我们能得到的最长1串长度为y此时我们能进行的最大操作数为k-x。我们定义mp[i]0串长度为i时1串的最长长度为mp[i]。然后我们更新mp[x]为max(mp[r-l1],y)即可。
因为这是0串在左1串在右所以我们还需要将字符串翻转然后再这样处理一次。
最后输出的时候每次我们只需要遍历mpa*imp[i]取max即可。
当然这样子操作的总复杂度是O(n^4)我们肯定是不能接受的那么怎么能让它复杂度降下来呢我们可以利用dp来预处理用dp[i][j]来表示[i~n]区间操作数最大为j时1串的最大长度。
具体实现见代码注释。
int n,k;
int mp[maxn];
//表示连续0的长度为i的时候最长连续1的长度最大为mp[i]
string x;
void f() {vectorvectorintdp(n2,vectorint(k2));//dp[i][j]表示[i~n]区间操作数最大为j时连续1的最大长度。 vectorintsum(n2);//sum[i]表示[1,i]中字符1的个数 string s x;//下标从1开始防止数组越界 for(int in; i1; i--) {//预处理出i~n的字符串在操作数为k时候变为1的最大连续串长度dp[i]dp[i1]; //大区间可以由小区间的方案转移过来 ,因为在相同操作数下[i,n]的最长连续1串 [i1,n]的最长连续1串 int cost0;for(int ji; jn; j) {cost(s[j]0);if(costk) dp[i][cost]max(dp[i][cost],j-i1);//如果合法则答案取max else break;//后面的cost都大于k了直接break }for(int j1; jk; j) dp[i][j]max(dp[i][j],dp[i][j-1]);//大的操作数方案可以由小的操作数方案转移过来因为你用x次操作能办到的用x1次操作也一定能办到 }mp[0]max(mp[0],dp[1][k]);//将全是1没有0的情况特殊处理 for(int i1; in; i)sum[i]sum[i-1](s[i]1);//预处理前缀1的个数 for(int i1; in; i) {for(int ji; jn; j) {if(sum[j]-sum[i-1]k)continue;//如果操作数大于k了则不合法continue mp[j-i1]max(mp[j-i1],dp[j1][k-sum[j]sum[i-1]]);//j-i1为连续0的长度k-sum[j]sum[i-1]为剩下的操作数 }}
}
void solve() {cinnkx;for(int i0; in; i) mp[i]-1;//初始化为-1 f();//处理0串在左1串在右的情况 reverse(x.begin(),x.end()),f();//等于处理1串在左0串在右的情况 for(int i1; in; i) {int ans0;for(int j0; jn; j) {//当0的长度为j时 if(mp[j]!-1)ansmax(ans,i*jmp[j]);}coutans ;}coutendl;
}
