SPOJ.COM - Thuật toán bài ANARC05B - The Double HeLiX

Posted on October 31st, 2016

Đề bài:

Cho 2 dãy số nguyên hữu hạn, tăng nghiêm ngặt. Bất kì những số nguyên nào giữa 2 dãy thì đều tạo nên điểm giao nhau giữa hai dãy. Ví dụ với 2 dãy sau, những điểm giao nhau là những điểm được in đậm:

  • Dãy 1: 3 5 7 9 20 25 30 40 55 56 57 60 62
  • Dãy 2: 1 4 7 11 14 25 44 47 55 57 100

Bạn có thể di chuyển giữa hai dãy bằng cách sau:

  • Cách 1. Bạn bắt đầu từ điểm đầu của 1 trong 2 dãy. Rồi di chuyển về phía trước.
  • Cách 2. Tại điểm nối, bạn có 2 sự lựa chọn là tiếp tục di chuyển trên dãy đó, hoặc là chuyển sang dãy mới.

Mục đích là tìm ra đường đi cho ra tổng các ô bạn đi là lớn nhất. Trong ví dụ trên tổng lớn nhất là 450, nó là kết quả của việc đi theo đường:

3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, và 62

Đầu vào

Có nhiều testcase, mỗi cái được xác định trên 2 dòng. Mỗi dòng biểu diễn một dãy và có định dạng:

n v1 v2 ... vn

Trong đó, n là độ dài của dãy, vi là phần tử thứ i của dãy. Mỗi dãy sẽ có ít nhất 1 phần tử nhưng không lớn hơn 10000. Tất cả phần tử đều thuộc từ -10000 đến 10000 (bao gồm 2 giá trị biên). Dòng cuối cùng của đầu vào sẽ là số 0, và nó không thuộc vào các test case.

Đầu ra

Mỗi một test case, in ra trên một dòng giá trị lớn nhất có thể.

Ví dụ

Đầu vào:

13 3 5 7 9 20 25 30 40 55 56 57 60 62
11 1 4 7 11 14 25 44 47 55 57 100
4 -5 100 1000 1005
3 -12 1000 1001
0

Đầu ra:

450
2100

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

Phân tích

  • Ở đây, mình kết hợp 2 thuật toán là: thuật toán chia để trị Divide and conquerthuật toán quy hoạch động Dynamic programming để giải quyết bài toán.

  • Thuật toán chia để trị nhằm mục đích tìm ra thành phần chung nhau của 2 dãy. Ý tưởng ở đây là với mỗi số thuộc dãy 1. Mình sẽ sử dụng tìm kiếm nhị phân để tìm ra vị trí của nó trong dãy số 2. Kết quả là mình xác định được vị trí trùng nhau của các phần tử trên 2 dãy.

  • Thuật toán quy hoạch động là để tìm ra giá trị lớn nhất tại mỗi điểm khi đi từ đầu đến cuối dãy. Một điều chú ý ở đây là tại mỗi dãy, ở các điểm trùng nhau ta có thể đi sang nhau. Do đó, giá trị lớn nhất tại 2 điểm trùng nhau khi ta đi từ đầu dãy đến đó là bằng nhau và bằng giá trị lớn nhất của 2 phần tử ở hai dãy.

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 = 10005;

int N[2];           // Lưu số chiều dài của 2 dãy
int Seq[2][MAX];    // Lưu thông tin 2 dãy
int Common[2][MAX]; // Lưu id thành phần chung của 2 dãy
int NumCmn;         // Độ dài thành phần chung 2 dãy
int First, Second;  // Dãy ngắn hơn gọi là First, dãy còn lại là Second
int MaxSum[2][MAX]; // Tính giá trị lớn nhất tại mỗi điểm khi đi từ đầu

/*
* Tìm trong mảng a, độ dài leng, phần tử có giá trị k
* RETURN: chỉ số của phần tử k trong mảng nếu tìm thấy, ngược lại là -1
*/
int BinarySearch(int *a, int leng, int k)
{
	int left = 1, right = leng, mid = 0;
	while(left < right)
	{
		mid = (left + right) / 2;
		if(a[mid] == k) return mid;

		if(a[mid] > k) right = mid - 1;
		else left = mid + 1;
	}
	if(a[left] == k) return left;
	return -1;
}

int main(int argc, char** argv)
{
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);

	cin >> N[0];

	while(N[0] != 0)
	{
		// Nhập đầu vào
		for(int i = 1; i <= N[0]; i++)
			cin >> Seq[0][i];
		cin >> N[1];
		for(int i = 1; i <= N[1]; i++)
			cin >> Seq[1][i];

		// Tìm dãy ngắn hơn
		if(N[0] < N[1]) First = 0;
		else First = 1;
		Second = 1 - First;

		// Duyệt dãy ngắn hơn để tìm ra thành phần chung
		NumCmn = 0;
		for(int i = 1; i <= N[First]; i++)
		{
			// Tìm trong dãy hai, vị trí của 1 số có giá trị ở dãy 1 đang xét
			int t = BinarySearch(Seq[Second], N[Second], Seq[First][i]);

			// Nếu tìm thấy
			if(t != -1)
			{
				NumCmn += 1;
				Common[First][NumCmn] = i;
				Common[Second][NumCmn] = t;
			}
		}

		// Tìm giá trị lớn nhất tại mỗi điểm bằng cách đi từ đầu
		MaxSum[First][0] = 0;
		MaxSum[Second][0]= 0;
		for(int c = 1; c <= NumCmn; c++)
		{
			for(int i = Common[First][c-1]; i < Common[First][c]; i++)
				MaxSum[First][i + 1] = MaxSum[First][i] + Seq[First][i + 1];

			for(int i = Common[Second][c-1]; i < Common[Second][c]; i++)
				MaxSum[Second][i + 1] = MaxSum[Second][i] + Seq[Second][i + 1];

			int t = max(MaxSum[First][Common[First][c]], MaxSum[Second][Common[Second][c]]);
			MaxSum[First][Common[First][c]] = MaxSum[Second][Common[Second][c]] = t;
		}

		for(int i = Common[First][NumCmn]; i < N[First]; i++)
			MaxSum[First][i + 1] = MaxSum[First][i] + Seq[First][i + 1];
		for(int i = Common[Second][NumCmn]; i < N[Second]; i++)
			MaxSum[Second][i + 1] = MaxSum[Second][i] + Seq[Second][i + 1];

		// In kết quả
		cout << max(MaxSum[First][N[First]], MaxSum[Second][N[Second]]) << endl;
		cin >> N[0];
	}
	return 0;//Your program should return 0 on normal termination.
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé: