UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#203873#3571. 最优匹配lsr100631ms6644kbC++11679b2024-03-24 11:40:382024-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