2024 -- 星航计划 --十一月份 -- 基础算法
每一段连续的 \(1\) 之间是独立的，我们只需要关心一段连续的 1 的结果。可以证明对于一段连续的 \(1\) ，最优策略是将其划分成多个单独的 \(1\) 以及可能余下的连续两个 \(1\)。
- 对于 \(k\) 个连续的 \(1\) ，如果 \(k\) 是奇数，最优策略是将其划分为 \(\frac{k+1}{2}\) 个单独的 \(1\) ，答案为 \(\frac{k+1}{2}\) ;
- 否则最优策略是将其划分为 \(\frac{k}{2}-1\) 个单独的 \(1\) 和两个连续的 \(1\) ，答案为与 \(\frac{k}{2}-1+\sqrt{2}\) 。
时间复杂度 \(O(|S|)\) 。
#include <bits/stdc++.h>
#define int long long
using ll = long long;
using pll = std::pair<int, int>;
using namespace std;
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
string s;
cin >> s;
int n = s.size();
s = ' ' + s + '0';
vector<int> per(n + 3);
vector<int> k;
double ans = 0;
for (int i = 1; i <= n + 1; ++i){
if (s[i] == '1')
per[i] = per[i - 1] + 1;
else
if (per[i - 1])
k.push_back(per[i - 1]);
}
for (int i : k){
while (i > 2){
i -= 2;
ans += 1;
}
ans += sqrt(double(i));
}
cout << fixed << setprecision(13) << ans;
return 0;
}