自己的电脑做服务器搭建网站,网址查询器,公司企业宣传片制作公司,wordpress企业文化模板下载题意#xff1a;给一串数字#xff0c;问长度为m的严格上升子序列有多少个 解法#xff1a;首先可以离散化为10000以内#xff0c;再进行dp#xff0c;令dp[i][j]为以第i个元素结尾的长度为j的上升子序列的个数#xff0c; 则有dp[i][j] SUM(dp[k][j-1]) (a[k] a[… 题意给一串数字问长度为m的严格上升子序列有多少个 解法首先可以离散化为10000以内再进行dp令dp[i][j]为以第i个元素结尾的长度为j的上升子序列的个数 则有dp[i][j] SUM(dp[k][j-1]) (a[k] a[i] k i) 不可能直接遍历所以考虑优化可以看出dp方程相当于一个区间求和所以可以用树状数组来优化。 代码 #include iostream
#include cmath
#include iostream
#include cstdio
#include cstring
#include cstdlib
#include cmath
#include algorithm
#define SMod 123456789
#define lll __int64
using namespace std;
#define N 10007lll c[N],a[N],b[N];
int n,m;
lll dp[N][104];int lowbit(int x)
{return x (-x);
}void modify(int pos,lll val)
{while(pos n){c[pos] val;pos lowbit(pos);}
}lll getsum(int pos)
{lll res 0;while(pos 0){res (resc[pos])%SMod;pos - lowbit(pos);}return res;
}int main()
{int i,j;while(scanf(%d%d,n,m)!EOF){for(i1;in;i){scanf(%I64d,a[i]);b[i] a[i];}sort(b1,bn1);memset(dp,0,sizeof(dp));for(i1;in;i)dp[i][1] 1;for(j2;jm;j){memset(c,0,sizeof(c));for(i1;in;i){int ind lower_bound(b1,bn1,a[i])-b;dp[i][j] getsum(ind-1);modify(ind,dp[i][j-1]);}}lll ans 0;for(i1;in;i)ans (ans dp[i][m])%SMod;printf(%I64d\n,ans);}return 0;
} View Code 转载于:https://www.cnblogs.com/whatbeg/p/3961018.html
