UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#196954#2464. 附魔tkswls100200ms1988kbC++111.3kb2023-11-04 10:00:432023-11-04 12:09:31

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
long long n, a[305], sum[305], f[305][305], err[305];
const long long inf = 2147483648;
bool cmp(int p, int q) {
	return p > q;
}
inline int calc(int p, int q) {
	int op = p / q, cnt = 0;
	cnt = err[op] * (q - p % q);
	cnt += err[op + 1] * (p % q);
	if (cnt >= inf) return inf;
//	cout << p << " " << q << ' ' << cnt << "[]\n";
	return cnt;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	sort(a + 1, a + n + 1, cmp);
	for (int i = n; i >= 1; i--) {
		sum[i] = sum[i + 1] + a[i];
	}
	err[0] = 1;
	for (int i = 1; i <= n; i++) {
		err[i] = err[i - 1] * 2;
		if (err[i] > inf) err[i] = inf + 1;
	}
	for (int i = 0; i <= n; i++) err[i]--;
	f[1][1] = sum[2];
	int p, q;
	for (int i = 2; i <= n; i++) {
		for (int j = i ; j >= 2; j--) {
			p = i - j + 1;
			f[i][p] = inf;
			for (int k = j - 1; k >= 1; k--) {
				if (k == 1 && j != 2) break;
				q = j - 1 - k + 1;
				f[i][p] = min(f[i][p], f[j - 1][q] + calc(p, q) + sum[i + 1]);
			}
//			cout << i << ' ' << p << "^" << f[i][p] << "\n";
		}
	}
	int ans = inf;
	for (int i = 1; i < n; i++) {
		ans = min(ans, f[n][i]);
	}
	if (ans > 2147483647) {
		cout << "Too expensive!";
		return 0;
	}
	cout << ans;
}

详细

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

Test #1:

score: 10
Accepted
time: 0ms
memory: 1268kb

input:

3
5 2 5

output:

10

result:

ok 1 number(s): "10"

Test #2:

score: 10
Accepted
time: 0ms
memory: 1312kb

input:

18
18 43 13 4 43 7 38 20 12 41 33 6 23 23 41 11 21 15

output:

596

result:

ok 1 number(s): "596"

Test #3:

score: 10
Accepted
time: 0ms
memory: 1320kb

input:

20
12 6 37 42 10 6 36 50 17 41 8 40 13 46 20 0 34 16 45 11

output:

711

result:

ok 1 number(s): "711"

Test #4:

score: 10
Accepted
time: 0ms
memory: 1380kb

input:

46
45 47 62 18 59 91 43 33 59 9 21 25 61 12 4 58 3 65 90 65 30 15 92 53 64 62 63 43 68 37 79 63 60 1...

output:

4123

result:

ok 1 number(s): "4123"

Test #5:

score: 10
Accepted
time: 1ms
memory: 1388kb

input:

50
96 8 61 33 39 25 65 26 25 0 32 100 75 80 18 13 4 91 31 5 64 79 68 65 78 39 37 67 34 26 83 27 49 9...

output:

4448

result:

ok 1 number(s): "4448"

Test #6:

score: 10
Accepted
time: 34ms
memory: 1864kb

input:

253
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

252

result:

ok 1 number(s): "252"

Test #7:

score: 10
Accepted
time: 49ms
memory: 1976kb

input:

300
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

299

result:

ok 1 number(s): "299"

Test #8:

score: 10
Accepted
time: 40ms
memory: 1936kb

input:

279
72 7 40 86 86 33 61 23 48 95 80 5 58 13 95 47 34 35 76 62 55 45 36 85 7 48 33 48 53 69 15 29 40 ...

output:

34359

result:

ok 1 number(s): "34359"

Test #9:

score: 10
Accepted
time: 22ms
memory: 1808kb

input:

224
48 17 62 41 26 21 44 82 39 62 48 3 15 33 94 76 88 19 64 2 10 98 18 38 53 95 74 30 83 46 23 43 24...

output:

28384

result:

ok 1 number(s): "28384"

Test #10:

score: 10
Accepted
time: 54ms
memory: 1988kb

input:

300
38 74 14 80 92 86 6 27 29 21 41 52 78 7 17 73 64 4 57 95 32 97 24 96 60 79 37 12 7 61 77 89 98 6...

output:

36952

result:

ok 1 number(s): "36952"

Extra Test:

score: 0
Extra Test Passed