天津网站建设哪家做得好,网站集约化建设的讲话,app开发公司倒闭了怎么办,广西建筑模板递增子序列
金牌导航 数据结构优化DP-1
题目大意
给出一个序列#xff0c;让你求长度为m的单调递增子序列的个数
输入样例
3 2
1 1 2
7 3
1 7 3 5 9 4 8输出样例
2
12数据范围 1⩽n⩽104,1⩽m⩽100,0⩽ai⩽9876543211\leqslant n \leqslant 10^4,1\leqslant m \leqslant…递增子序列
金牌导航 数据结构优化DP-1
题目大意
给出一个序列让你求长度为m的单调递增子序列的个数
输入样例
3 2
1 1 2
7 3
1 7 3 5 9 4 8输出样例
2
12数据范围
1⩽n⩽104,1⩽m⩽100,0⩽ai⩽9876543211\leqslant n \leqslant 10^4,1\leqslant m \leqslant 100,0\leqslant a_i \leqslant 9876543211⩽n⩽104,1⩽m⩽100,0⩽ai⩽987654321
解题思路
对于第i个数如果要使以它结尾的单调递增子序列长度为j那么就要在前面找到比aia_iai小的数累加以它们为结尾长度为j-1的单调递增序列就是把i接到后面 如果直接DP枚举会TLE 这时可以用树状数组在O(logn)O(logn)O(logn)的时间内求出累加的值没计算出一个数就加进树状数组中
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 100010
#define wyc 123456789//orz
using namespace std;
int n, m, l, x, a[N], b[N], c[101][N];
void add(int g, int x, int y)
{for (; x l; x x-x)c[g][x] (c[g][x] y) % wyc;
}
int ask(int g, int x)
{int y 0;for (; x; x - x-x)y (y c[g][x]) % wyc;return y;
}
int main()
{while(~scanf(%d%d, n, m)){memset(c, 0, sizeof(c));for (int i 1; i n; i){scanf(%d, a[i]);b[i] a[i];}sort(a 1, a 1 n);l unique(a 1, a 1 n) - a - 1;//离散化for (int i 1; i n; i){x lower_bound(a 1, a 1 l, b[i]) - a;for (int j m; j 1; --j)add(j, x, ask(j - 1, x - 1));//求累加值再加到树状数组中add(1, x, 1);}printf(%d\n, ask(m, l));}return 0;
}
