python/TangDou/KaoShi/投篮游戏II.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;
int a[N];
int n;
//最大值
int cnt;
//路径
vector<int> path;
/**
 测试用例：
 3
 130 200 55

 最多投进球的个数
 答案：2
 */

/**
 * 功能：深度优先搜索
 * @param step    选择了哪个篮筐
 */
void dfs(int step) {
    //如果越界
    if (step == n + 1) {
        //更新最大长度
        cnt = max(cnt, (int) path.size());
        return;
    }

    //如果选择了当前篮筐
    //是不是可以选择这个位置
    if (path.empty() || a[step] < a[path.back()]) {
        path.push_back(step);//选择了第几个篮筐
        dfs(step + 1);
        path.pop_back();//回溯
    }
    //不选择当前篮筐
    dfs(step + 1);
}

int main() {
    //输入
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    //深度优先
    dfs(1);
    //输出最大值
    cout << cnt << endl;
    return 0;
}