A37145. 投篮N个篮筐，投球到篮筐。玩法如下：规则1，第1次投篮，可以投任意篮筐。规则2，第2次及以后，每次投上次后面的蓝筐。规则3，第2次及以后，每次只能投比上次更近的篮筐。给出N个篮筐的距离和顺序，求最多能投进几个球。如3个篮筐的距离和顺序为130，200，55。有3种投法：1）第1次投130，那么投130，55，最多投进2球。2）第2次投200，那么投200，55，最多投进2球。3）第2次投55，那…
填空题
困难
知识点
题目描述
投篮
N个篮筐，投球到篮筐。玩法如下：
规则1，第1次投篮，可以投任意篮筐。
规则2，第2次及以后，每次投上次后面的蓝筐。
规则3，第2次及以后，每次只能投比上次更近的篮筐。
给出N个篮筐的距离和顺序，求最多能投进几个球。
如3个篮筐的距离和顺序为130，200，55。有3种投法：
1）第1次投130，那么投130，55，最多投进2球。
2）第2次投200，那么投200，55，最多投进2球。
3）第2次投55，那么投55，最多投进1球。
因此，按照规则，最多可投进2球。
样例输入
3
130 200 55
样例输出
2
参考答案
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,a[1005],dp[1005];
//投篮(动规-最长下降子序列)
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int maxn=0;
for(int i=0;i<n;i++){
dp[i]=1;
for(int j=0;j<i;j++)
if(a[i]<a[j]) dp[i]=max(dp[i],dp[j]+1);
maxn=max(maxn,dp[i]);
}
cout<<maxn<<endl;
return 0;
}
上一题
下一题