题目传送门
本题最大难点：读题。
首先说一下题意：
有 $w$ 堆货物，第 $i$ 堆有 $b_i$ 个，从上往下给定每个货物的进价。
所有货物的售价都是 $10$，但是如果想买一件货物，必须要先买在它上面的所有货物。
求出最大利润，以及要达成这个利润，需要买多少个货物，可能有多种方案，从小到大输出。如果超过 $10$ 个只需要输出最小的 $10$ 个。
显然先把每堆的前缀和从大到小排序，最大利润就是每堆 rk1 的前缀和加起来。
比较烦的是有的堆前缀和可能 $\le 0$。
这里有个小 trick：每堆在排序时加一个元素 $(0,0)$，表示前 $0$ 个的利润和是 $0$。这样就可以挤掉 $\le 0$ 的情况。
接下来处理货物数。
最小就是每堆 rk1 的长度的和，贪心计算出接下来最小的方案是什么：遍历一遍现有的所有方案，算出所有拓展的方式取 min，然后把这种方案加到答案队伍里。要去重。已经有 $10$ 个不重复的就 break。
注意：
- $b$ 有可能是 $0$
- 输出格式，每组数据之间要空一行
- 实在不行去 udebug 上找组数据测测
加了 IO 优化才过。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| vector<vector<pair<int, int> > >v;
int rk[20000][55];
void solve() {
v.resize(n);
cnt = 0;
rep(i, n) {
cin >> m;
sum = 0;
v[i].clear();
v[i].pb(mp(0, 0));
rep(j, m) {
cin >> a;
sum += 10 - a;
v[i].pb(mp(-sum, j + 1));
}
sort(v[i].begin(), v[i].end());
}
sum = 0;
rep(i, n)sum -= v[i][0].fi;
ans = 1;
cnt = 1;
init(rk[0], 0);
rep(i, n) rk[0][n] += v[i][0].se;
rep(I, 10000) {
int mn = MAXN, id1, id2;
rep(i, ans) {
rep(j, n) {
if (rk[i][j] < 0 || rk[i][j] >= (int)v[j].size() - 1 || v[j][rk[i][j] + 1].fi != v[j][rk[i][j]].fi)continue;
if (rk[i][n] + v[j][rk[i][j] + 1].se - v[j][rk[i][j]].se < mn) {
mn = rk[i][n] + v[j][rk[i][j] + 1].se - v[j][rk[i][j]].se;
id1 = i;
id2 = j;
}
}
}
if (mn == MAXN)break;
rep(i, n)rk[ans][i] = rk[id1][i];
rk[ans][id2]++;
rk[id1][id2] = -1;
rk[ans][n] = mn;
if (rk[ans][n] != rk[ans - 1][n])cnt++;
ans++;
if (cnt == 10)break;
}
cout << "Workyards " << T_ << endl;
cout << "Maximum profit is " << sum << ".\n";
cout << "Number of pruls to buy:";
rep(i, ans)if (!i || rk[i][n] != rk[i - 1][n])cout << ' ' << rk[i][n];
cout << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
T_ = 1;
while (cin >> n) {
if (!n)break;
if (T_ > 1)cout << endl;
solve();
T_++;
}
return 0;
}
|
另一种也许可行的办法
爆搜出所有方案，放到 set 里去找到前十。上次 CSP-J 被 set 坑到 TLE ，就没敢用。