ABC468F
2026-07-26 22:26:18
发布于：广东
27阅读
0回复
0点赞
F
会了，显然 ， 是上升的，考虑维护两个线程一个一个记录最大值，一个存普通值求 ，我们会发现只要出现一个能更新最大值的数就一定要更新，否则一定不优
证明：令当前两个线程为 ，考虑新加进来一个数 ，考虑两种情况，两个策略：
1.
- A：更新最大值，变为 ，
- B：放到普通数组里，变为 ，
- 对比：发现因为递增，显然 ，在后续答案的更新上显然不优
2.
- A：很显然丢到这无法使答案增加
- B：而放到普通数组里去影响 LIS 显然更好
由此这种做法是对的
时间复杂度瓶颈 求
#include <bits/stdc++.h>
using namespace std;
namespace CZW
{
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
void Main()
{
int n; cin>>n;
int ans=0,mx=0;
vec<int> v;
for (int i=1;i<=n;++i) {
int x; cin>>x;
if (x>mx) {
++ans;
mx=x;
}else v.pb(x);
}
vec<int> tail;
for (int x:v){
auto it=lower_bound(tail.begin(),tail.end(),x);
if (it==tail.end()) tail.pb(x);
else *it=x;
}
cout<<ans+tail.size();
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int Test = 1;
// cin >> Test;
while (Test--)
CZW::Main();
return 0;
}
有帮助，赞一个