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

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;
int a[N];
int n;
//最大值
int Max;

/**
 测试用例：
 3
 130 200 55

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

/**
 * 功能：深度优先搜索
 * @param step      选择了哪个篮筐
 * @param last      前面最后一个数字是多少
 * @param cnt       已经投中了多少个球
 */
void dfs(int u, int last, int cnt) {
    //如果越界
    if (u == n + 1) {
        //更新最大长度
        Max = max(Max, cnt);
        return;
    }

    //如果可以选择当前篮筐，并且选择了当前篮筐
    if (a[u] < last)
        dfs(u + 1, a[u], cnt + 1);

    //放弃当前篮筐
    dfs(u + 1, last, cnt);
}

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