詳細解釋點擊：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（树状数组）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。