微信网站主题,网络建设解决方案,电子商务他们的代表网站,公司邮箱怎么登陆依据问题转换成最长不降子序列问题。 10^9的输入数据计算起来还是挺花时间的。由于这里仅仅能使用O(nlgn)时间复杂度了。只是证明是能够算出10^9个数据的。由于时间限制是5s. #include stdio.h
#include vector
#include string.h
#include algori… 依据问题转换成最长不降子序列问题。 10^9的输入数据计算起来还是挺花时间的。由于这里仅仅能使用O(nlgn)时间复杂度了。只是证明是能够算出10^9个数据的。由于时间限制是5s. #include stdio.h
#include vector
#include string.h
#include algorithm
#include iostream
#include string
#include limits.h
#include stack
#include queue
#include set
#include map
using namespace std;const int MAX_N 20;
vectorint arr, a2;
int N;inline int lSon(int rt) { return rt1|1; }
inline int rSon(int rt) { return (rt1)2; }void postOrder(int rt, int v)
{int l lSon(rt), r rSon(rt);if (l N) postOrder(l, v);if (r N) postOrder(r, v);a2.push_back(arr[rt]-v);
}int biGetIndex(int low, int up, int v)
{while (low up){int mid low ((up-low)1);if (v a2[mid]) up mid-1;else low mid1;}return low;
}int LIS()
{int j 0;for (int i 1; i N; i){if (a2[i] a2[j]) a2[j] a2[i];else{int id biGetIndex(0, j, a2[i]);a2[id] a2[i];}}return j1;
}int main()
{int a;scanf(%d, N);arr.clear(), a2.clear();while (scanf(%d, a) ! EOF){arr.push_back(a);}N (int) arr.size();int v 0;postOrder(0, v);int len LIS();printf(%d\n, N-len);return 0;
} 转载于:https://www.cnblogs.com/lytwajue/p/6758611.html
