[Thuật toán] Trò chơi với băng số – LINEGAME

Link đề:vn.spoj.com/problems/LINEGAME/
Đề bài:
Có một băng hình chữ nhật được chia làm n ô vuông đánh số từ trái qua phải bắt đầu từ 1. Trên ô vuông thứ i người ta ghi một số nguyên dương ai, i = 1,2,…,n. Ở mỗi lượt chơi, người tham gia được quyền lựa chọn một số lượng tùy ý các ô trên băng số. Giả sử theo thứ tự từ trái qua phải, người chơi lựa chọn các ô i1, i2,…, ik. Khi đó điểm số mà người chơi đạt được là:

Yêu cầu: Hãy tính số điểm lớn nhất có thể đạt được từ một lượt chơi.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên dương n ( n ≤ 10⁶ ) là số lượng ô của băng số;
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n ( a_i ≤ 10⁴, i = 1, 2, …, n ) ghi trên băng số. Các số liên tiếp trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách.

Kết quả:

• Một số nguyên duy nhất là số điểm lớn nhất có thể đạt được từ một lượt chơi.

Ví dụ:

Ý tưởng:(Ý tưởng mang tính chất tham khảo, code của mình chỉ chạy được 80 điểm)

Để có thể chọn được tập các số sao cho tổng hiệu xen kẽ lớn nhất như đề bài nêu thì chúng ta chúng ta sẽ sử dụng theo cách tìm các điểm cực đại và các điểm cực tiểu, lấy tổng các điểm cực đại trừ đi tổng các điểm cực tiểu là ra kết quả cần tìm và lưu ý là không lấy các điểm cực tiểu ở đầu và cuối nếu có (chỉ lấy cực đại thôi). Cụ thể như hình vẽ sau:

#include <cstdio>
#include <cstdlib>
#include <fstream>
#include <iostream>

#define INP "LINEGAME.INP"
#define OUT "LINEGAME.OUT"

using namespace std;

int main() {

	ifstream inp(INP);
	ofstream out(OUT);
	int n = 0;

	cin >> n;
	
	if (n==1){
		//cout << "n = 1";
		cin >> n;
		cout << n;
		return 0;
	}
	
	int* a = (int *) malloc(n * sizeof(int));
	//cout << n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		//cout << a[i] << " ";
	}
	//cout << endl;

	

	long sum = 0;
	int min = 0;
	
	for (int j = 0; j < n; j++) {
		// tim diem cuc dai
		if (j < n) {	
			sum -= min;	// tru di diem cuc tieu truoc do
//			cout << sum << " = " << "sum  - " << min << endl;
			while (j < n - 1 && a[j] < a[j + 1]) {
				j++;
			}
			sum += a[j]; // cong diem cuc dai vao
//			cout << sum << " = " << "sum  + " << a[j] << endl;
		}
		
		// tim diem cuc tieu, khong lay diem cuoi cung
		if (j < n - 1) {
			while (j < n - 1 && a[j] > a[j + 1]) {
				j++;
			}
			min = a[j]; // ghi lai de neu co cuc dai thi moi tru
		}
	}
	cout << sum <<endl;

	return 0;
}

Ngoài ra mình có tham khảo và hỏi các bạn đã làm đựoc 100 điểm, các bạn noi như thế này mà vẫn chưa hiểu:

Gọi d0[i] là chọn a[i] hoặc không và đặt trc nó cái dấu cộng gọi d1[i] là chọn hay k chọn a[i] đặt nó là dấu trừ
d1[i]:=max(d1[i-1],d0[i-1]-a[i]);
d0[i]:=max(d1[i-1]+a[i],d0[i-1]);