UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203854#3571. 最优匹配smallstone1001846ms30848kbC++111.5kb2024-03-24 10:42:262024-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;
}

Details

小提示:点击横条可展开更详细的信息

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