链接螺纹:vn.spoj.com/problems/LINEGAME/
主题:
有一矩形频带被划分为从左至右开始编号为n的正方形 1. 人们第i个平方谁记录了一个正整数, 我= 1,2，…,ñ. 在每局, 参与者可以选择在冰上的细胞的任意数量的. 假设顺序从左至右, 玩家选择单元格i1, i2，…, 我. 那么玩家获得的分数是:

要求: 计算游戏可能获得的最大积分.

数据:

• 第一行包含正整数n ( n≤ 10⁶ ) 是磁带的单元数;
• 第二行包含n个正整数a₁, 该₂, …, 该_ñ ( 该_在 ≤ 10⁴, I = 1, 2, …, ñ ) 记录在数字磁带上. 同一行上的连续数字至少要用一个空格隔开.

结果:

• 一个整数，即一个回合可以获得的最大点数.

例:

这个想法:(想法仅供参考, 我的代码就可以了 80 点)

为了能够选择一组数字，以使最大交替总和达到上述要求，我们将以找到最大和最小点的方式使用它, 从最小点的总和中减去最小点，并注意在起点和终点都没有最小点（如果有）。 (就拿最大). 具体如下图:

#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;
}

我也有参考，请问你做了 100 点, 如果你这样说，我还是不明白:

致电d0[在] 是选择一个[在] 是否将其放在称为d1的加号上[在] 是选择还是k选择一个[在] 把它减号
D1[在]:= MAX(D1[I-1],d0[I-1]-该[在]);
d0[在]:= MAX(D1[I-1]+该[在],d0[I-1]);