算法

(DP) $O(n^2)$

题意：

从一维棋盘的起点跳到终点，只能从左到右跳，中间有很多棋子，每个棋子都有值。可以选择从起点跳到任意一个棋子，然后从当前位置跳到一个比该棋子值大的位置；或者从一个棋子跳到终点，当然也可以直接从起点跳到终点，求一种跳法使得经过的棋子的值之和最大。

分析：

对于第 $i$ 个棋子，可以从起点跳到这个位置，也可以从前面一个比该棋子值小的位置跳过来。定义 f[i] 表示跳到第 $i$ 个位置时能够得到的棋子的值之和，只需找到一个 $f$ 值最大的 $j$，满足 $j < i$ 且棋子 $j$ 的值小于棋子 $i$ 即可。如果不存在则直接从起点跳到该点。由于任意一步可以选择跳到终点，所以每次计算都需要更新最终结果。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::max;
using ll = long long;

bool chmax(ll& a, ll b) { if (a < b) { a = b; return 1; } return 0; }

const int N = 1010;

ll a[N], f[N];

int main() {
    int n;

    while (cin >> n, n) {
        rep(i, n) cin >> a[i];
        std::memset(f, 0, sizeof f);
        ll ans = 0;
        rep(i, n) {
            f[i] = a[i];
            rep(j, i) {
                if (a[i] > a[j])
                    chmax(f[i], f[j] + a[i]);
            }
            chmax(ans, f[i]);
        }
        cout << ans << '\n';
    }

    return 0;
}