ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#203854 | #3571. 最优匹配 | smallstone | 100 | 1846ms | 30848kb | C++11 | 1.5kb | 2024-03-24 10:42:26 | 2024-03-24 12:04:19 |
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
//using LL = __int128
ll n, a[1111];
ld dp[1111][1111], dis[1111][1111], f[1111][1111];
int main(){
scanf("%lld", &n);
for(int i = 1 ; i <= 2 * n ; i++){
scanf("%lld", a + i);
}
sort(a + 1, a + 1 + 2 * n);
for(int i = 1 ; i <= 2 * n ; i++)
for(int j = i + 1 ; j <= 2 * n ; j++){
dis[i][j] = sqrt(a[j] - a[i]);
//printf("%.10Lf%c", dis[i][j], " \n"[j == 2 * n]);
}
for(int len = 2 ; len <= 2 * n ; len += 2){
for(int i = 1 ; i + len - 1 <= 2 * n ; i++){
int l = i, r = i + len - 1;
dp[l][r] = dis[l][r] + dp[l + 1][r - 1];
for(int i = l + 2 ; i <= r - 2 ; i += 2)
dp[l][r] = min(dp[l][r], dis[l][r] + dp[l + 1][i] + dp[i + 1][r - 1]);
}
}
//*
for(int i = 1 ; i <= 2 * n ; i++)
for(int j = 1 ; j <= 2 * n ; j++)
f[i][j] = 1e10;
//*/
for(int len = 2 ; len <= 2 * n ; len += 2){
for(int i = 1 ; i + len - 1 <= 2 * n ; i++){
int l = i, r = i + len - 1;
f[l][r] = min(dp[l][r], dis[l][r] + f[l + 1][r - 1]);
for(int i = l + 1 ; i <= r - 1 ; i += 2){
f[l][r] = min(f[l][r], f[l][i] + f[i + 1][r]);
//cout << l << " " << r << " " << f[l][r] << "\n";
}
}
}
/*
ld ans = dp[1][2 * n];
for(int i = 2 ; i < 2 * n ; i += 2){
printf("%.10Lf %.10Lf %.10Lf\n", ans, dp[1][i], dp[i + 1][2 * n]);
ans = min(ans, dp[1][i] + dp[i + 1][2 * n]);
}
printf("%.10Lf\n", ans);
//*/
printf("%.10Lf\n", f[1][2 * n]);
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1312kb
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: 0ms
memory: 1376kb
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: 1492kb
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: 1492kb
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: 2756kb
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: 2756kb
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: 4ms
memory: 2756kb
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: 618ms
memory: 30848kb
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: 633ms
memory: 30848kb
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: 591ms
memory: 30848kb
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