苏州网站推广如何,深圳网络推广深圳网,网站建设3d插件,织梦医院网站模板题意
让我们在数串统计最长长度的LIS有多少个 每个LIS元素没有重叠
分析
这题可以用nlogn的LIS方法水过 就是每次我们更新找到的LIS长度的时候 就把当前位置下的元素标记 表示我们把它删掉了 不断地重复找LIS的过程 最后如果找到的长度小于我们最初找到的LIS长度 就退出循…题意
让我们在数串统计最长长度的LIS有多少个 每个LIS元素没有重叠
分析
这题可以用nlogn的LIS方法水过 就是每次我们更新找到的LIS长度的时候 就把当前位置下的元素标记 表示我们把它删掉了 不断地重复找LIS的过程 最后如果找到的长度小于我们最初找到的LIS长度 就退出循环 复杂度大概在Onumber of LIS * n * logn
code #includebits/stdc.h
using namespace std;
vectorintv,ans;
mapint,intbok;//由于数据范围不明确直接用map比较省内存
int main()
{int n;while(~scanf(%d,n)){for(int i1;in;i){int t;scanf(%d,t);v.push_back(t); }int Ma 0,res0,at0;while(1){Ma0;// 初始化为0 ans.clear();ans.push_back(-1);// 保证一定能查到元素下界for(int i0;in;i){if(bok[i])continue; if(v[i]ans[ans.size()-1])ans.push_back(v[i]),Ma,bok[i]1;else if(v[i]ans[ans.size()-1]){int pos lower_bound(ans.begin(),ans.end(),v[i])-ans.begin();ans[pos] v[i];}} if(Mares)res Ma,at1;else if(Mares)at;else if(Mares)break;}printf(%d\n%d\n,res,at);bok.clear();ans.clear();v.clear(); }return 0;
}
一开始没发现有多组 。。。 读题啊。。。
