hdu-Find the nondecreasing subsequences（树状数组）

详细解释点击：here~~

离散化  ++++ dp思想

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std;const int mod = 1000000007; int a[100010]; int n; struct node {int x,y; }s[100010];bool cmp(node p,node q) {if(p.x == q.x) return p.y < q.y;return p.x < q.x; } int lowbit(int x) {return x&(-x); } void add(int pos,int num) {while(pos <= n){a[pos] = (a[pos] + num) % mod;pos += lowbit(pos);} } int getsum(int pos) {int res = 0;while(pos > 0){res = (res + a[pos]) % mod;pos -= lowbit(pos);}return res; } int main() {while(scanf("%d",&n)!=EOF){memset(a,0,sizeof(a));memset(s,0,sizeof(s));for(int i = 1;i <= n;i++){scanf("%d",&s[i].x);s[i].y = i;}sort(s+1,s+n+1,cmp);int temp = 0;for(int i = 1;i <= n;i++){temp = getsum(s[i].y) + 1;temp %= mod;add(s[i].y,temp);}printf("%d\n",getsum(n));} }

总结

以上是生活随笔为你收集整理的hdu-Find the nondecreasing subsequences（树状数组）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。