解决51nod1376题，通过线段树优化动态规划，计算数组中不同最长递增子序列的数量。输入数组经过排序与去重，并利用线段树查询和更新区间内的最长递增子序列及其数量。
51nod 1376 最长递增子序列的数量
数组A包含N个整数（可能包含相同的值）。设S为A的子序列且S中的元素是递增的，则S为A的递增子序列。如果S的长度是所有递增子序列中最长的，则称S为A的最长递增子序列（LIS）。A的LIS可能有很多个。例如A为：{1 3 2 0 4}，1 3 4，1 2 4均为A的LIS。给出数组A，求A的LIS有多少个。由于数量很大，输出Mod 1000000007的结果即可。相同的数字在不同的位置，算作不同的，例如 {1 1 2} 答案为2。
Input
第1行：1个数N，表示数组的长度。(1 <= N <= 50000)
第2 - N + 1行：每行1个数A[i]，表示数组的元素(0 <= A[i] <= 10^9)
Output
输出最长递增子序列的数量Mod 1000000007。
Input示例
5
1
3
2
0
4
Output示例
2
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
|
/*
51nod 1376 最长递增子序列的数量
题目大意：中文题面自己看
思路:LIS的问题做过很多次,求数量是第一次,用常规的dp来做很好写,但数据范围50000是会超时的,于是可以用线段树维护区间的最长长度与其个数
1.
首先将输入的数组进行排序,比如说
那么我们创建两个数组a1与a2,a1存储原数组，a2进行排序
即:a1[5]=1 2 2 0 4,a2[5]=0 1 2 2 4;
然后再将a2[5]去重,得到a2[4]=0 1 2 4;
2.
以a2数组的大小为区间建树build(1,0,4-1=3);
再查找a1[i](i=0...4)在a2中的上界pos,用lower_bound函数可以直接查找;
定义nlen与nnum记忆目前的最大长度与数量
query(1,0,pos)(查询当输入a1[i]的时候的最长长度与其数量);
若查询的长度大于nlen则更新nlen与nnum;
最后更新线段树;
代码如下:
#include<cstdlib> #include<cstring> #include<iostream> #define lson i<<1 #define rson i<<1|1 #define ll long long #include<algorithm> using namespace std; const ll mod = 1000000007; const int maxn = 50010; int a[maxn]; int a1[maxn]; typedef struct{ int l,r,num,len; //num为最长长度的方案的数量,len为最长的长度 }TREE; TREE tree[maxn*4]; ll llen,lnum; void push_up(int i) { if(tree[lson].len == tree[rson].len) { tree[i].len = tree[lson].len; tree[i].num = tree[lson].num + tree[rson].num; tree[i].num %= mod; } else if(tree[lson].len > tree[rson].len) { tree[i].len = tree[lson].len; tree[i].num = tree[lson].num; } else { tree[i].len = tree[rson].len; tree[i].num = tree[rson].num; } } void build(int i,int l,int r) { tree[i].l=l; tree[i].r=r; tree[i].num=tree[i].len=0; if(l==r) { return; } int mid=(l+r)>>1; build(lson,l,mid); build(rson,mid+1,r); push_up(i); } void gengxin(int i,int k,ll len2,ll num2) { if(tree[i].l==tree[i].r&&tree[i].l==k) { if(tree[i].len<len2) { tree[i].len=len2; tree[i].num=num2; } else if(tree[i].len==len2) { tree[i].num+=num2; tree[i].num%=mod; } else {} return; } int mid=(tree[i].l+tree[i].r)/2; if(k <= mid) gengxin(lson,k,len2,num2); else gengxin(rson,k,len2,num2); push_up(i); } void query(int i,int l,int r) { if(l > r) { llen = 0,lnum = 1; return ; } if(tree[i].l >= l && tree[i].r <= r) { if(llen == -1) llen = tree[i].len,lnum = tree[i].num; else { if(llen == tree[i].len) lnum += tree[i].num; else if(llen < tree[i].len) { llen = tree[i].len,lnum = tree[i].num; } lnum %= mod; } return ; } int mid = (tree[i].l+tree[i].r)/2; if(l <= mid) query(lson,l,r); if(r > mid) query(rson,l,r); return; } int cnt=0; int tlen,ans; int main() { int N; scanf("%d",&N); for(int i=0;i<N;i++) { scanf("%d",&a[i]); a1[i]=a[i]; } sort(a,a+N); cnt=0; for(int i=1;i<N;i++) { if(a[i]!=a[cnt]) { a[++cnt]=a[i]; } } build(1,0,cnt); ans = 0; tlen = 0; int id = lower_bound(a,a+cnt+1,a1[0]) -a; gengxin(1,id,1,1); tlen=1; ans=1; for(int i=1;i<N;i++) { id=lower_bound(a,a+cnt+1,a1[i])-a; //找到t[i]在a数组中的位置 llen=-1; lnum=0; query(1,0,id-1); if(llen==0&&lnum==0) { lnum=1; } // printf("llen=%lld,lnum=%lld\n",llen,lnum); if(tlen<llen) //当前记录的最长长度比这次查询的长度短 { tlen=llen; //更新当前的最长长度 ans=lnum; //更新当前最长长度的数量 } else if(tlen==llen) //当前记录的最长长度与这次查询的长度相等 { ans+=lnum; } else //当前记录的最长长度比这次查询的长度长 { //不管他继续下一步 } ans%=mod; gengxin(1,id,llen+1,lnum); } printf("%d\n",ans); return 0; } |
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
