网站模板的修改,网站流量太大打不开怎么办,湖南鸿泰电力建设有限公司网站,申请网站空间是申请域名吗一、问题描述
P1020 [NOIP1999 提高组] 导弹拦截
二、问题简析
该题要我们求两个问题#xff1a;
1、不上升子序列的最大长度2、不上升子序列的最少个数
利用 D i l w o r t h Dilworth Dilworth 定理#xff0c;我们得到不上升子序列的最少个数等于上升子序列的最大长…一、问题描述
P1020 [NOIP1999 提高组] 导弹拦截
二、问题简析
该题要我们求两个问题
1、不上升子序列的最大长度2、不上升子序列的最少个数
利用 D i l w o r t h Dilworth Dilworth 定理我们得到不上升子序列的最少个数等于上升子序列的最大长度。
现在就是求这两个问题
1、不上升子序列的最大长度2、上升子序列的最大长度 类比最长上升子序列我们可以得到求最长不上升子序列的方法。与最长上升子序列不同点
1、 d p [ i ] dp[i] dp[i] 都初始化为 0 0 02、 d p [ i ] dp[i] dp[i] 是非升序所以要用 *upper_bound(dp1, dp1 cnt, A[i], greaterint()) A[i] 更新3、最终结果为 lower_bound(dp1, dp1 cnt, 0, greaterint()) - dp1 AC代码
#include bits/stdc.husing namespace std;
typedef long long ll;int quickin(void)
{int ret 0;bool flag false;char ch getchar();while (ch 0 || ch 9){if (ch -) flag true;ch getchar();}while (ch 0 ch 9 ch ! EOF){ret ret * 10 ch - 0;ch getchar();}if (flag) ret -ret;return ret;
}const int MAX 1e5 3;
const int INF 1e8;
int dp1[MAX], dp2[MAX], A[MAX];int main()
{#ifdef LOCALfreopen(test.in, r, stdin);#endifint num, cnt 0;while (cin num)A[cnt] num;fill(dp2, dp2 cnt, INF);for (int i 0; i cnt; i){*upper_bound(dp1, dp1 cnt, A[i], greaterint()) A[i];*lower_bound(dp2, dp2 cnt, A[i]) A[i];}cout lower_bound(dp1, dp1 cnt, 0, greaterint()) - dp1 endl;cout lower_bound(dp2, dp2 cnt, INF) - dp2 endl;return 0;
}完
