#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
int N, G;
double pref[15][15][100005], suf[15][15][100005], cost[15][1 << 15], dp[1 << 15];
string s;
bool cmp(int i, int mask, int mid)
{
double pre = 0, su = 0;
for (int j = 0; j < G; j++)
if (mask & (1 << j))
{
pre += pref[i][j][mid];
su += suf[i][j][mid + 1];
}
pre += pref[i][i][mid];
su += suf[i][i][mid + 1];
return pre < su;
}
double sum(int i, int mask, int mid)
{
double res = 0, pre = 0, su = 0;
for (int j = 0; j < G; j++)
if (mask & (1 << j))
res += pref[i][j][mid] + suf[i][j][mid + 1];
res += pref[i][i][mid] + suf[i][i][mid + 1];
return res;
}
signed main()
{
cin >> s;
N = s.size();
s = " " + s + " ";
for (int i = 1; i <= N; i++)
G = max(G, s[i] - 'A' + 1);
for (int i = 0; i < G; i++)
{
int acc[15] = {};
for (int j = 1; j <= N; j++)
{
if (s[j] - 'A' == i)
for (int k = 0; k < G; k++)
pref[i][k][j] += (i == k ? 0.5 * acc[k] : 1.0 * acc[k]);
acc[s[j] - 'A']++;
for (int k = 0; k < G; k++)
pref[i][k][j] += pref[i][k][j - 1];
}
}
for (int i = 0; i < G; i++)
{
int acc[15] = {};
for (int j = N; j >= 1; j--)
{
if (s[j] - 'A' == i)
for (int k = 0; k < G; k++)
suf[i][k][j] += (i == k ? 0.5 * acc[k] : 1.0 * acc[k]);
acc[s[j] - 'A']++;
for (int k = 0; k < G; k++)
suf[i][k][j] += suf[i][k][j + 1];
}
}
// for(int i = 0; i < G; i++)
// for(int j = 0; j < G; j++)
// {
// cout << i << " " << j;
// for(int k = 0; k <= N; k++)
// cout << " " << pref[i][j][k] << " " << suf[i][j][k] << ",";
// cout << '\n';
// }
for (int i = 0; i < G; i++)
for (int mask = 0; mask < (1 << G); mask++)
if ((mask & (1 << i)) == 0)
{
cost[i][mask] = 1e10;
// cout << i << " ";
int L = 0, R = N;
while (R > L)
{
int mid = (L + R) / 2;
if (cmp(i, mask, mid))
L = mid;
else
R = mid;
}
cost[i][mask] = min(cost[i][mask], sum(i, mask, L));
// bitset<4> b = mask;
// cout << '\n';
}
for (int mask = 0; mask < (1 << G); mask++)
{
dp[mask] = (mask == 0 ? 0.0 : 1e10);
for (int i = 0; i < G; i++)
if (mask & (1 << i))
dp[mask] = min(dp[mask], dp[mask ^ (1 << i)] + cost[i][mask ^ (1 << i)]);
}
cout << fixed << setprecision(10) << dp[(1 << G) - 1] << '\n';
}
Compilation message
passes.cpp: In function 'double sum(int, int, int)':
passes.cpp:29:18: warning: unused variable 'pre' [-Wunused-variable]
29 | double res = 0, pre = 0, su = 0;
| ^~~
passes.cpp:29:27: warning: unused variable 'su' [-Wunused-variable]
29 | double res = 0, pre = 0, su = 0;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2089 ms |
340 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2074 ms |
340 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2074 ms |
340 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2089 ms |
340 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |