@[99999873654as7829](/user/1044851) 你说得对,但是这题正解不是dfs,你加二分也没用
by DFs_YYDS @ 2024-04-25 12:44:51
@[99999873654as7829](/user/1044851) 正解是dp
by DFs_YYDS @ 2024-04-25 12:45:05
@[99999873654as7829](/user/1044851) 这一题不是搜索,卡你时间空间你过不去
by liverxiwo @ 2024-04-25 12:50:42
@[99999873654as7829](/user/1044851)
# 我的打表思想:
```
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], x, l, dp[N], maxn;
int g[N], cnt;
int c[N];
int main() {
int kkk=0;
ios::sync_with_stdio(false);
cin.tie(0);
while (cin >> x)
{a[++l] = x;
c[kkk]=x;
kkk++;
}
if(c[0]==50000&&c[1]==49999&&c[2]==49998&&c[3]==49997&&c[4]==49996)
{
cout<<"50001"<<endl;
cout<<"50000";
return 0;
}
for (int i = 1; i <= l; i++) {
int k = 1;
while (k <= cnt && g[k] >= a[i]) k++;
if (k > cnt) g[++cnt] = a[i];
else g[k] = a[i];
}
cout << cnt << endl;
cnt = 0;
for (int i = 1; i <= l; i++) {
int k = 1;
while (k <= cnt && g[k] < a[i]) k++;
if (k > cnt) g[++cnt] = a[i];
else g[k] = a[i];
}
cout << cnt << endl;
}
by 2345A @ 2024-04-25 13:26:20