SPOJ.COM - Thuật toán bài DCEPC501 - Save Thy Toys

Đầu bài:

Leonard rất yêu thích việc mua sắm những đồ chơi khoa học viễn tưởng hiếm và đắt. Anh ta giữ chúng theo một dãy theo thứ tự ngày mua và để trong một cái tủ. Vì vậy, Sheldon sẽ không bao giờ lấy được đồ chơi của anh ta. Nhưng vì một lần không may mắn, Leonard đã thu Sheldon trong một vụ cá cược. Và Sheldon đã yêu cầu Leonard chia sẻ đồ chơi. Bởi vì, Leonard không muốn mất nhiều tiền nên anh ta đã quyết định dựa trên một chiến lược để giảm thiểu sự mất mát xuống thấp nhất.

Leonard bắt đầu chọn từ đồ chơi đầu tiên ở trong tủ, sẽ lấy một số đồ chơi, gọi là 'x' đồ chơi. Sheldon sau đó sẽ chọn 'x' đồ chơi (chú ý là Sheldon sẽ chọn số đồ chơi bằng với Leonard, trừ khi số đồ chơi còn lại nhỏ hơn 'x'). Việc này sẽ tiếp tục cho đến khi không còn lại đồ chơi nào nữa.

Bạn được đưa cho một dãy của đồ chơi với giá của chúng. Hãy giúp Leonard lấy được đồ chơi với số tiền lớn nhất có thể. Leonard chỉ có thể chọn 1, 2 hay 3 đồ chơi ('x' có giá trị 1, 2 hay 3)

Đầu vào:

Dòng đầu tiên là T, số lượng testcase. Mỗi testcase chứa N ở dòng đầu tiên. Dòng thứ 2 là N số nguyên là giá tiền của các đồ chơi.

Đầu ra:

In ra 1 số nguyên trên một dòng cho mỗi test case là tổng số tiền lớn nhất của các đồ chơi mà Leonard chọn.

Ràng buộc:

1 <= T <= 10 
1 <= N <= 100000 
1 <= Giá của đồ chơi <= 1000000

Ví dụ:

Đầu vào:

2
4
5 4 3 2
6
10 8 7 11 15 20

Đầu ra:

12
53

Giải thích:

• Ở test case 1: Leonard chọn 3 đồ chơi trong lần đầu tiên của anh ta là: 5, 4, 3. Do đó, Sheldon không còn lựa chọn nào khác nên phải chọn 2. Khi đó, Leonard thu được tổng số tiền lớn nhất là 5 + 4 + 3 = 12

• Ở test case 2: Leonard chọn 10 và 8. Sau đó, Sheldon chọn 7 và 11. Cuối cùng Leonard chọn 15 và 20. Do đó, số tiền lớn nhất mà Leonard thu được là: 10 + 8 + 15 + 20 = 53

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/DCEPC501/

Phân tích:

Ở đây, mình sử dụng thuật toán quy hoạch động Dynamic programming để giải quyết bài toán. Và cách triển khai là kiểu bottom-up (tức là sử dụng vòng lặp). Có một vài điều cần chú ý ở đây là:

• Leonard sẽ có 3 cách lựa chọn là: chọn 1, 2 hoặc 3 vật.
• Kết quả có thể rất lớn nên phải sử dụng kiểu long long (64 bit) để lưu kết quả

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/ C++

#include <iostream>
using namespace std;

const int MAX = 1000010;

int N;                      // Số đồ chơi
int Price[MAX];             // Giá của các đồ chơi
long long MaxMoney[MAX];    // MaxMoney[i] là số tiền lớn nhất
                            // khi Leonard chọn từ đồ chơi thứ i.
int main(int argc, char** argv)
{
	int T, test_case;
	ios::sync_with_stdio(false);
	//freopen("input.txt", "r", stdin);

	cin >> T;
	for(test_case = 0; test_case  < T; test_case++)
	{
		// Nhập đầu vào
		cin >> N;
		for(int i = 1; i <= N; i++)
		{
			cin >> Price[i];
			MaxMoney[i] = 0;
		}

		// Trường hợp cơ sở
		MaxMoney[N] = Price[N];
		for(int i = N + 1; i <= N + 5; i++)
			Price[i] = MaxMoney[i] = 0;

		for(int i = N-1; i >= 1; i--)
		{
			// Nếu chọn 1 đồ chơi
			MaxMoney[i] = (long long)Price[i] + MaxMoney[i + 2];

			// Nếu chọn 2 đồ chơi
			long long t = (long long)(Price[i] + Price[i + 1]) + MaxMoney[i + 4];
			if(t > MaxMoney[i]) MaxMoney[i] = t;

			// Nếu chọn 3 đồ chơi
			t = (long long)(Price[i] + Price[i + 1] + Price[i + 2]) + MaxMoney[i + 6];
			if(t > MaxMoney[i]) MaxMoney[i] = t;
		}
		cout << MaxMoney[1] << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}