ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#203873 | #3571. 最优匹配 | lsr | 100 | 631ms | 6644kb | C++11 | 679b | 2024-03-24 11:40:38 | 2024-03-24 12:06:35 |
answer
#include <bits/stdc++.h>
using namespace std;
#define QwQ3301AwA return 0
#define ll long long
int n;
int a[1000];
double f[805][805];
bool vis[805][805];
double dfs(int l, int r) {
if (l > r) return 0;
if (l + 1 == r) return sqrt(a[r] - a[l]);
if (vis[l][r]) return f[l][r];
vis[l][r] = 1;
f[l][r] = 1e14;
for (int k = r - 1; k >= l; k -= 2) {
f[l][r] = min(f[l][r], dfs(l, k - 1) + dfs(k + 1, r - 1) + sqrt(a[r] - a[k]));
}
return f[l][r];
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= 2 * n; i++) cin >> a[i];
sort(a + 1, a + 2 * n + 1);
printf("%.10lf", dfs(1, 2 * n));
QwQ3301AwA;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1320kb
input:
3 759701 719733 839866 896910 588337 796328
output:
792.7065369214
result:
ok found '792.7065369', expected '792.7065369', error '0.0000000'
Test #2:
score: 10
Accepted
time: 1ms
memory: 1336kb
input:
6 42677 333562 438423 74943 411905 424147 224732 440713 242486 736422 332521 397152
output:
1073.2676452290
result:
ok found '1073.2676452', expected '1073.2676452', error '0.0000000'
Test #3:
score: 10
Accepted
time: 0ms
memory: 1388kb
input:
10 282491 230980 401907 481241 256336 466811 183048 322957 294440 458143 5835 294862 362921 342954 1...
output:
1865.4020874953
result:
ok found '1865.4020875', expected '1865.4020875', error '0.0000000'
Test #4:
score: 10
Accepted
time: 0ms
memory: 1384kb
input:
10 511453 931069 124700 917930 467911 911168 756527 902515 391381 110878 933351 956902 574602 156512...
output:
1754.7001220371
result:
ok found '1754.7001220', expected '1754.7001220', error '0.0000000'
Test #5:
score: 10
Accepted
time: 0ms
memory: 1796kb
input:
50 454758 23915 135868 121403 808691 250077 260403 73322 66701 47192 881463 50911 35029 285471 71961...
output:
4490.6936799495
result:
ok found '4490.6936799', expected '4490.6936799', error '0.0000000'
Test #6:
score: 10
Accepted
time: 0ms
memory: 1796kb
input:
50 674126 310179 932211 866560 574506 480189 525183 480352 608110 185340 882726 189967 399247 261996...
output:
4260.0947805901
result:
ok found '4260.0947806', expected '4260.0947806', error '0.0000000'
Test #7:
score: 10
Accepted
time: 0ms
memory: 1796kb
input:
50 790254 859024 936956 752934 923760 958966 488655 664340 542265 522226 175870 749711 199338 55725 ...
output:
4237.4461394433
result:
ok found '4237.4461394', expected '4237.4461394', error '0.0000000'
Test #8:
score: 10
Accepted
time: 205ms
memory: 6640kb
input:
400 83612 218738 396752 849448 616304 522356 60348 628924 188489 83605 99730 977895 243831 81239 200...
output:
3356.1032160245
result:
ok found '3356.1032160', expected '3356.1032160', error '0.0000000'
Test #9:
score: 10
Accepted
time: 209ms
memory: 6644kb
input:
400 851385 264608 874852 154189 264606 762612 874862 363093 741052 852036 251183 942515 798377 40328...
output:
2529.8446361142
result:
ok found '2529.8446361', expected '2529.8446361', error '0.0000000'
Test #10:
score: 10
Accepted
time: 216ms
memory: 6636kb
input:
400 147603 918608 962771 918626 838499 605594 605580 457148 672314 319179 457140 297166 934365 83464...
output:
3100.9939165226
result:
ok found '3100.9939165', expected '3100.9939165', error '0.0000000'
Extra Test:
score: 0
Extra Test Passed