本文主要是介绍给定长度为n的01串s，有两种操作：1、交换相邻的两个字符，花费为1e12；2、删除一个字符，花费为1e12 + 1，求使s不递减的最少花费，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
思路：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
#define lson p << 1
#define rson p << 1 | 1
const int maxn = 1e6 + 5, inf = 1e12, maxm = 4e4 + 5, mod = 998244353, N = 1e6;
int a[505][505], b[maxn];
// bool vis[maxn];
int n, m;
string s;
int cnt[maxn][2];void solve(){int res = 0;int k;int x;int q;// cin >> n;cin >> s;n = s.size();s = " " + s;for(int i = 1; i <= n; i++){cnt[i][0] = cnt[i - 1][0];if(s[i] == '0'){cnt[i][0]++;}}cnt[n + 1][1] = 0;for(int i = n; i >= 1; i--){cnt[i][1] = cnt[i + 1][1];if(s[i] == '1'){cnt[i][1]++;}}res = (n - cnt[1][1]) * (inf + 1);for(int i = 1; i <= n; i++){int tmp = 1e18;if(s[i] == '0'){tmp = (n - cnt[i][0] - cnt[i + 1][1]) * (inf + 1);}else{if(i + 1 <= n && s[i + 1] == '0'){tmp = inf + (n - cnt[i][0] - cnt[i + 1][1] - 2) * (inf + 1);}}res = min(res, tmp);}cout << res << '\n';
}signed main(){ios::sync_with_stdio(0);cin.tie(0);// fac[0] = 1;// for(int i = 1; i <= N; i++){// fac[i] = fac[i - 1] * i % mod;// }// inv[N] = qpow(fac[N], mod - 2);// for(int i = N - 1; i >= 0; i--){// inv[i] = inv[i + 1] * (i + 1) % mod;// }int T = 1;cin >> T;while (T--){solve();}return 0;
}这篇关于给定长度为n的01串s，有两种操作：1、交换相邻的两个字符，花费为1e12；2、删除一个字符，花费为1e12 + 1，求使s不递减的最少花费的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
