40WA蒟蒻求解
查看原帖
40WA蒟蒻求解
150525
qiao_li_pa楼主2023/10/18 21:09
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> a,ranks;//a为题目序列,ranks[i]为i处后最长上升序列长度
int ranked(int);
int main(){
	cin>>n;
	ranks.resize(n+1);
        a.resize(n+1);
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}//读入数据
	for(int i=n;i>=1;i--){
		ranks[i]=ranked(i); 
	}//将i处的最长上升序列长度赋值入ranks数组
        cout<<ranks[1]<<endl;//输出数据
}
int ranked(int x){//该函数用于确定x处最长上升序列长度
	if(x==n) return 1;//边界判断
	int maxn=1;
	for(int i=x;i<=n;i++){
		if(a[i]>a[x]){
            maxn=max(maxn,ranks[i]+1);
        }//状态转移方程
	}//向后搜索大于a[x]的值
	return maxn;
}

代码如上,带注释,使用的是dp逆推思路,请各位帮忙看看出错在哪

2023/10/18 21:09
加载中...