AcWing算法提高课 1.2.2 最长上升子序列模型(二)

1010 拦截导弹

思路

第一问很简单

第二问也很简单, 用贪心的思想解决, 搞一个单调栈即可

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;const int N = 200010, mod = 1e9 + 7;int n, m, k, x, y, z, ans, t;
int w[N], f[N], q[N];void solve()
{while (cin >> x){w[ ++ n] = x;}int ans = 0;for (int i = 1; i <= n; i ++ ){f[i] = 1;for (int j = 1; j < i; j ++ ){if (w[i] <= w[j])f[i] = max(f[i], f[j] + 1);}ans = max(ans, f[i]);}cout << ans << "\n";ans = 1;for (int i = 1; i <= n; i ++ ){int k = 1;while (w[i] > q[k] && k < ans) k ++;if (ans == k) ans ++;q[k] = w[i];}cout << ans - 1 << "\n";
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;
//	cin >> T;while (T -- ){solve();}
}