Wyf32627 @ 2024-08-29 09:24:26
#include <bits/stdc++.h>
using namespace std;
struct node
{
vector<int>l;
int n;
};
vector<int>a;
int maxn=INT_MIN,n;
void bfs()
{
queue<node>q;
node h,t;
for(int i=0;i<a.size();i++)//初始化第i个元素为最长上升子序列中的第一个元素
{
h.l.clear();
h.l.push_back(a[i]);
h.n=i;
q.push(h);
}
while(!q.empty())
{
h=q.front(),q.pop();
if(h.n==n) maxn=max(maxn,int(h.l.size()));
if(a[h.n+1]<=h.l[h.l.size()-1])//指针指的数<=序列的最后一个数
{
t.l=h.l,t.n=h.n+1;
while(a[t.n]<=t.l[t.l.size()-1])
{
t.l.pop_back();//方案1：删除原序列中<=当前指针的数，直到>
}
t.l.push_back(a[t.n]);
q.push(t);
t.l=h.l,t.n=h.n+1;
q.push(t);//方案2：原序列不变，指针+1;
}
else//指针指的数>序列的最后一个数
{
t.l=h.l,t.n=h.n+1;
t.l.push_back(a[t.n]);
q.push(t);
}
}
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
bfs();
cout<<maxn;
return 0;
}by cinCi @ 2024-08-29 09:41:22
qp
by DFs_YYDS @ 2024-08-29 10:37:35
@Wyf32627 其实你的结构体只需要保存序列的最后一个元素和长度就行了
by Wyf32627 @ 2024-08-29 10:53:01
@DFs_YYDS 这能实现吗？万一倒数第二个元素<=序列的元素呢？
by DFs_YYDS @ 2024-08-29 10:53:31
@Wyf32627 你等我一下
by DFs_YYDS @ 2024-08-29 11:00:13
@Wyf32627
#include<bits/stdc++.h>
using namespace std;
int n,a[5005],ans=1;
struct node{
int back;//最后一个元素的下标
int len;//序列长度
};
void bfs(){
queue<node> q;
for(int i=0;i<n;i++)q.push({i,1});
while(!q.empty()){
node h=q.front();
q.pop();
ans=max(ans,h.len);
for(int i=h.back+1;i<n;i++)if(a[i]>a[h.back])q.push({i,h.len+1});
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
bfs();
cout<<ans;
return 0;
}交上去AC+MLE，应该是队列爆掉了等我剪一下枝，但是应该都是对的
by DFs_YYDS @ 2024-08-29 11:01:34
@DFs_YYDS 其实bfs做这种题目性能很差，甚至不如剪枝的dfs
by _N00B_ @ 2024-08-29 11:07:52
我的建议是重新整理思路，再写一遍
首先 vector<int> a 就没有分配内存，输入的时候就RE了。
而且这里可能越界：
25 if(a[h.n+1]<=h.l[h.l.size()-1])这里可能会越界也没有判空：
27 t.l=h.l,t.n=h.n+1;
28 while(a[t.n]<=t.l[t.l.size()-1])
29 {
30 t.l.pop_back();
31 }这里也可能越界：
39 t.l=h.l,t.n=h.n+1;
40 t.l.push_back(a[t.n]);还有这个地方是不是应该continue一下：
24 if(h.n==n) maxn=max(maxn,int(h.l.size()));回顾你的思路，其实就是搜索以每一个元素开始的最长上升子序列，方式就是从每一个起始下标i开始，依次向后遍历元素并决定是否添加到该序列中，同时维护上升子序列的合法性，从而得到上升子序列的长度同时更新答案。其实这样的思路是没有什么错误的，只是代码实现有些问题而已。
但是仔细想想这样做不就是相当于遍历了每一种子序列了么？时间复杂度相比使用dfs进行子集枚举没有什么优势。甚至dfs还能写剪枝优化，也不需要每一次枚举都要O(n)维护上升子序列。
by Wyf32627 @ 2024-08-29 11:19:20
@DFs_YYDS @N00B 谢谢
by LagSuc @ 2024-09-07 15:48:34
果然只有橙名人发的贴才有人回吗，真是艰难
by LagSuc @ 2024-09-07 15:49:45
怎么样过了吗？我的dfs也是re。