Puoi leggere e provare a risolvere il problema pile
visitando la piattaforma Terry.
Hint 1. Se c'è una sola scatola (ovvero ), come conviene orientarla?
Hint 2. Nel caso generale, considera ciascuna scatola indipendentemente dalle altre.
Notiamo che conviene sempre orientare ogni scatola in modo che la sua altezza coincida con lo spigolo più lungo (o, in caso ve ne sia più di uno, uno qualunque di essi). Inoltre, così facendo l'altezza totale è indipendente dall'ordine delle scatole.
La risposta è quindi pari alla somma, per , di .
La complessità della soluzione è .
C++
#include <iostream>
#include <vector>
using namespace std;
void solve(int t) {
int N;
cin >> N;
vector<int> A(N), B(N), C(N);
for (int i = 0; i < N; i++)
cin >> A[i] >> B[i] >> C[i];
int ans = 0;
for (int i = 0; i < N; i++)
ans += max(A[i], max(B[i], C[i]));
cout << "Case #" << t << ": " << ans << "\n";
}
int main() {
int T;
cin >> T;
for (int t = 1; t <= T; t++) solve(t);
return 0;
}