EXPRESS - Biểu thức
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho ~n~ số nguyên dương ~a_i,i=1..n~, bạn phải đặt giữa ~n~ số nguyên dương này ~2~ phép nhân và ~n-3~ phép cộng sao cho kết quả biểu thức là lớn nhất.
Ví dụ: với ~n=5~ và dãy ~a_i~ là ~4, 7, 1, 5, 3~ thì bạn có thể có các biểu thức:
- ~4 + 71 + 53~;
- ~471 + 5 + 3~.
Chú ý: Không được thay đổi thứ tự xuất hiện của ~a_i,i=1..n~ trong biểu thức thu được.
Input
- Dòng đầu chứa số nguyên dương ~n\ (4≤n≤1000)~;
- ~N~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~a_i\ (1≤a_i≤10000,i=1..n)~.
Output
- Ghi ra một số nguyên dương duy nhất là giá trị lớn nhất của biểu thức thu được.
Sample
Input #1
5
4
7
1
5
3
Output #1
44
Hint
- Biểu thức thu được là: ~47 + 1 + 53~.
Problem source: Chuyên Sơn La Online Judge
Bình luận
Ý tưởng: Ta đi tìm 2 tích của các cặp lớn nhất sẽ ra được kết quả. Ta duyệt như sau (với sample #1): 4 7 1 5 3. Ta tính tổng tất cả các phần tử sẽ ra kết quả là 20. Sau đó lấy tổng này trừ đi các phần tử thuộc phép nhân rồi + với chính phép nhân đó để ra kết quả thay vì phải tính lại. Sử dụng 2 vòng for lồng nhau để duyệt.
4 * 7 * 1 + 5 + 3 = 36 (số 4, 7, 1 thuộc phép nhân (4 * 7 * 1 = 28) nên ta lấy 20 - (4 + 7 + 1) = 8, kết quả sẽ là 28 + 8 = 36)
4 * 7 + 1 * 5 + 3 = 36 (số 4, 7, 1, 5 thuộc phép nhân (4 * 7 + 1 * 5 = 33) nên ta lấy 20 - (4 + 7 + 1 + 5) = 3, kết quả sẽ là 33 + 3 = 36, tương tự các phần bên dưới).
4 * 7 + 1 + 5 * 3 = 44
4 + 7 * 1 * 5 + 3 = 42
4 + 7 * 1 + 5 * 3 = 26
4 + 7 + 1 * 5 * 3 = 26
Max của ta là 44 và đó là kết quả.