题解 | #Redraiment的走法#动态规划

总结状态规划方程为一句话：到【当前梅花桩的最大步数】为之前【高度小于当前梅花桩中的梅花桩】的最大步数+1。

即 dp[i] = max{ dp[0] ... dp[i - 1] } + 1, when val[0] < val[i] ... val[i - 1] < val[i] 。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    int val;
    vector<int> i_vec;
    for (int i = 0; i < n; ++i) {
        cin >> val;
        i_vec.push_back(val);
    }

    int max_pos = 0;
    vector<int> redraiment_vec(n, 1);
    for (int i = 0; i < n; ++i) {

        int pos_tmp = 0;    // 值小于当前梅花桩，但是步数最高的位置
        for (int j = 0; j < i; ++j) {
            if (i_vec[j] >= i_vec[i]) continue;
            if (redraiment_vec[j] >= redraiment_vec[pos_tmp]) pos_tmp = j;
        }

        if (i_vec[pos_tmp] < i_vec[i]) redraiment_vec[i] = redraiment_vec[pos_tmp] + 1;
        if (redraiment_vec[i] > redraiment_vec[max_pos]) max_pos = i;

    }

    cout << redraiment_vec[max_pos] << endl;
}
// 64 位输出请用 printf("%lld")