hdu 3030 Increasing Speed Limits(树状数组求最长上升子序列)
在前边关于DP总结的文章中说了通过普通的DP法个二分查找法求最长上升子问题,最近在学习BIT,然后突然发现原来通过BIT也可以求最长上升子序列问题。本来想着可以通过类似的方法在O(nlogn)时间内求出,然而题目的意思是求出总和,这样的话二分法就不好使了,一开始也没有理解,不过通过单纯的求最长上升子序列,终于搞明白了。先来看看求解普通的最长上升子序列问题:题目中首先将重复的元素去掉,以为我们求的是严格意义上的上升序列,因此,相同的元素是没有任何意义的,所以先对所有元素排序,然后去除掉重复元素。[cpp]#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=110000;int n,val[N],a[N];int len,arr[N];int lowbit(int x){return x&(-x);}//原始的updatevoid update(int i,int x){while(x<=len){if(i>arr[x])arr[x]=i;x+=lowbit(x);}}int query(int x){int ans=0;while(x){if(arr[x]>ans)ans=arr[x];x-=lowbit(x);}return ans;}int main(){while(~scanf("%d",&n)){for(int i=0;i<n;i++){scanf("%d",&val[i]);a[i]=val[i];}//排序去冲sort(a,a+n);len=unique(a,a+n)-a;memset(arr,0,sizeof(arr));int ans=1,tmp;for(int i=0;i<n;i++){//这里val中保存的是可以插入元素的位置val[i]=lower_bound(a,a+len,val[i])-a;tmp=query(val[i])+1;//tmp保存的是当前位置左边比它小的数的个数,注意这里要加1,因为第i结束时需要给序列加1if(tmp>ans)//取最大值,我们求得是最长上升的序列ans=tmp;update(tmp,val[i]+1);更新val[i]+1位置,注意tree中保存的是左边小的值,所以在真正求值时需要+1}printf("%d\n",ans);}return 0;}好了,搞明白了找个基本问题,杭电的这道题也就可以理解了:[cpp]#include <cstdlib>#include <cstring>#include <cstdio>#include <map>#include <algorithm>#define MOD 1000000007#define MAXN 500005using namespace std;int num[MAXN], A[MAXN], c[MAXN], seq[MAXN], cnt;inline int lowbit(int x){return x & -x;}//这里的update是正常的inline void update(int pos, int val){for (int i = pos; i <= cnt; i += lowbit(i)){c[i] += val;if (c[i] >= MOD)c[i] %= MOD;}}inline int getsum(int pos){int s = 0;for (int i = pos; i > 0; i -= lowbit(i)){s += c[i];if (s >= MOD)s %= MOD;}return s;}int main(){int T, n, m;long long X, Y, Z, res;scanf("%d", &T);for (int ca = 1; ca <= T; ++ca){res = 0;map<int,int>mp;scanf("%d %d %I64d %I64d %I64d", &n, &m, &X, &Y, &Z);memset(c, 0, sizeof (c));for (int i = 0; i < m; ++i){scanf("%d", &A[i]);}for (int i = 0; i < n; ++i){num[i+1] = A[i%m];seq[i] = num[i+1];A[i%m] = (X*A[i%m]+Y*(i+1))%Z;}//其中num和seq保存的值是一模一样的sort(num+1, num+1+n);//去除临近元素,cnt表示的是一共有多少个不同的元素//这里进行的是离散化的操作,对于最长上升子序列来说,相同元素是毫无意义的cnt = unique(num+1, num+1+n) - (num+1);for (int i = 1; i <= cnt; ++i){//上边是通过二分找位置,这里使用的map来记录位置mp[num[i]] = i;}update(1, 1);for (int i = 0; i < n; ++i){ //注意这里是累加,而上边的代码中是取最大值long long x = getsum(mp[seq[i]]);res += x;if (res > MOD) 补充:软件开发 , C++ ,
上一个:图论算法模板整理
下一个:poj1007 qsort快排
- 更多C/C++疑问解答:
- 关于c++的cout输出的问题。
- 在学校里学过C和C++,不过学的很一般,现在自学C#,会不会很难?
- 全国计算机二级C语言笔试题
- 已知某树有2个2度结点,3个3度结点,4个4度结点,问有几个叶子结点?
- c++数据结构内部排序问题,整数排序
- 2012九月计算机二级C语言全国题库,,急求急求
- 如果assert只有一个字符串作为参数,是什么意思呢?
- C语言中,哪些运算符具有左结合性,哪些具有右结合性,帮忙总结下,谢谢了!
- 为什么用结构体编写的程序输入是,0输不出来啊~~~
- 将IEEE—754的十六进制转化为十进制浮点类型,用C或C++都行,多谢各位大侠啊,非常感谢!
- 为什么这个程序求不出公式?
- 这个链表倒置的算法请大家分析下
- c语言函数库调用
- C语言unsigned int纠错
- C语言快排求解啊