思路：分析可知，在最优解的情况下，反转和（替换+反转）次数是一样的，那么我们只要统计总的需要反转的个数。最后再比较反转和替换价值的大小即可。 利用贪心思想，最后肯定是一次性替换是最好的。
/** * From: * Qingdao Agricultural University * Created by XiangwangAcmer * Date : 2019-10-31-10.12.37 * Talk is cheap.Show me your code. */ #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cstdlib> #include<queue> #include<cmath> #include<cctype> #include<stack> #include<map> #include<string> #include<cstdlib> #define ll long long using namespace std; const ll maxn = 1e6 + 5; const ll minn = 1e9 + 5; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; const long long LIMIT = 4294967295LL; vector<int>v[maxn]; int dp[maxn]; vector<int>G[maxn]; bool row[maxn], col[maxn]; bool flag = 0; queue<int>q; int a[maxn]; string L; int main() { ios::sync_with_stdio(false); int n; ll fz, th; ///分析可知，在最优解的情况下，反转和（替换+反转）次数是一样的 cin >> n; cin >> fz >> th; cin >> L; int cnt = 0; ll sum = 0; for(int i = 0; i < n; i++)///需要操作的总次数 { if(L[i] == '1') { sum += cnt; cnt = 0; continue; } cnt = 1; } sum += cnt; if(sum == 0) { cout << 0 << endl; return 0; } if(fz >= th) cout << sum * th << endl; else cout << (sum - 1) * fz + th << endl; return 0; }