hdu4991 树状数组+dp
2024-09-03 11:02:59
这题说的是给了一个序列长度为n 然后求这个序列的严格递增序列长度是m的方案有多少种,如果用dp做那么对于状态有dp[n][m]=dp[10000][100],时间复杂度为n*m*n接受不了那么想想是否可以再这个上加些什么样的优化。树状数组 对于每个值离散在树状数组中然后对于每个点都有以他为结尾点的递增序列的长度为1..100,那么他的状态是怎么来的呢?当他的i长度的是等于在他前面比他来的小的 长度为i-1的的种数,然后得到了这个值将他在加进这第i棵树状数组中然后就得到解了,不断地进行这个过程时间n*m*log2(n);
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
typedef int ll;
const int MAX_N = ;
const ll MOD = ;
ll C[][MAX_N];
ll A[MAX_N],B[MAX_N];
int len;
int lowbit(int x){
return x&(-x);
}
void add(int x,ll value, int floor){
while(x<=len){
C[floor][x]=(C[floor][x]+value)%MOD;
x+=lowbit(x);
}
}
ll sum(int x, int floor){
ll ans=;
while(x>){
ans=(ans+C[floor][x])%MOD;
x-=lowbit(x);
}
return ans;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)==){ for(int i=; i<n; ++i){
scanf("%d",&A[i]);
B[i] = A[i];
}
sort( B , B + n );
len = unique(B,B+n)-B;
memset(C,,sizeof(C));
for(int i =; i<n; ++i){
int loc = lower_bound(B,B+len,A[i])-B+;
add(loc,,);
for(int j = ; j<=m ; ++j ){
ll num = sum(loc-,j-);
add(loc,num,j);
}
}
ll ans = sum(len,m);
printf("%d\n",ans);
}
return ;
}
最新文章
- swift 命名,字符串
- [USACO1.1]坏掉的项链Broken Necklace
- swift枚举
- Mysql 删除语句
- JavaScript调试技巧之console.log()详解
- 使用CSS3(一)
- SharePoint 2013 创建web应用程序报错&;quot;This page can’t be displayed&;quot;
- Vnix项目正式启动
- live555—VS2010/VS2013 下live555编译、使用及测试(转载)
- CSS3之background-clip
- mongoDB 大文件存储方案, JS 支持展示
- Hyper-V
- Luogu P2613 【模板】有理数取余
- liunx 安装jdk1.8
- JVM调优原理
- 2018.11.05 bzoj2143: 飞飞侠(最短路)
- kubernetes(k8s) 的常用命令
- Spring Security教程(一):初识Spring Security
- ROS的工作模式和ESXI网卡工作模式的关系
- Flask从入门到精通之flask扩展
热门文章
- Linux大文件已删除,使用df查看已使用的空间并未减少
- windows_xp下卸载office2003报无法打开此修补程序包错误
- C++ 输入/输出
- traceroute 排查 nginx 反向代理 配置
- Connections in Galaxy War----zoj3261
- mysql 权限管理 针对某个库 某张表 授权 tables_priv表
- myeclipse maven工程调试调试
- 使用免费的Let&#39;s Encrypt通配符证书 升级我们的网站
- 为什么要用Markov chain Monte Carlo (MCMC)
- scipy模块