1085 - All Possible Increasing Subsequences
Time Limit:3 second(s)
|
Memory Limit:64 MB
|
An increasing subsequence from a sequenceA1, A2... Anis defined byAi1, Ai2... Aik, where the following properties hold
1.i1< i2< i3< ... < ikand
2.Ai1< Ai2< Ai3< ... < Aik
Now you are given a sequence, you have to find the number of all possible increasing subsequences.
Input
Input starts with an integerT (≤ 10), denoting the number of test cases.
Each case contains an integern (1 ≤ n ≤ 105)denoting the number of elements in the initial sequence. The next line will containnintegers separated by spaces, denoting the elements of the sequence. Each of
these integers will be fit into a 32 bit signed integer.
Output
For each case of input, print the case number and the number of possible increasing subsequences modulo1000000007.
Sample Input
|
Output for Sample Input
|
3
3
1 1 2
5
1 2 1000 1000 1001
3
1 10 11
|
Case 1: 5
Case 2: 23
Case 3: 7
|
Notes
1.For the first case, the increasing subsequences are(1), (1, 2), (1), (1, 2), 2.
2.Dataset is huge, use faster I/O methods.
题目大意:找出一个序列中的所有上升序列,很容易想到DP,直接给代码,注释里有说明:
/**
** 构造n的状态空间, dp[i]表示以i结尾的所有上升序列的个数
** 转移为 dp[i] = 1+segma(dp[k])| 0<=k<i && arr[k]<arr[i]
** 不用树状数组优化的话转移是O(n)的
** 用树状数组优化以后转移就是O(logn)的,需要离散化
**/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const int MAXN = 100010;
int c[MAXN],arr[MAXN],pt[MAXN],t,n,m;
LL ans,MOD = 1000000007ll,dp[MAXN];
void init(){
memset(c,0,sizeof(c));
ans = 0;
}
int lowbit(int x){
return x&(-x);
}
int sum(int pos){
int s = 0;
while(pos>0){
s = (s+c[pos])%MOD;//不取模的话会溢出
pos-=lowbit(pos);
}
return s;
}
void add(int pos,int val,int n){
while(pos<=n){
c[pos] = (c[pos]+val)%MOD;//不取模的话会溢出
pos+=lowbit(pos);
}
}
//离散化
void disc(){
memcpy(pt,arr,sizeof(arr));
sort(pt,pt+n);
int i;
for(i=1,m=1;i<n;i++){
if(pt[i]!=pt[i-1])pt[m++]=pt[i];
}
}
int search(int k){
int l=0,r=m-1,m;
while(l<=r){
m = (l+r)>>1;
if(pt[m]==k)return m;
else if(k<pt[m])r=m-1;
else l=m+1;
}
return -1;
}
int main(){
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
init();
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&arr[i]);
disc();
dp[0] = 1;ans = 1;
add(search(arr[0])+1,dp[0],m);
for(int i=1;i<n;i++){
int pos = search(arr[i])+1;
dp[i] = (sum(pos-1)+1)%MOD;
ans = (ans+dp[i])%MOD;
add(pos,dp[i],m);
}
printf("Case %d: %lld\n",cas,ans);
}
return 0;
}
分享到:
相关推荐
LightOJ-已解决代码我所有的Light Online Judge的解决问题代码。
轻描淡写 像Codeforces编辑模式一样在lightoj上发表社论!
LightOJ-solutions
leetcode中国 数据结构和算法编码 议程 :balloon: 不是为了比赛,而是为了训练和兴趣。 Python3 你可以在这里找到我的 LeetCode 解决方案:(等待打开) ...LightOJ 1012 --- dfs transform 13. HDU 1495 --- compl
LightOJ
解析编程问题,并将其发送给CHelper插件以实现IntelliJ IDEA。 竞争性伴侣解析程序...-HackerRank-HDU在线法官-Kattis-LightOJ-NYTD在线法官-PEG法官-POJ-QDUOJ-Timus-URI在线法官 支持语言:English (United States)
问题教程:一个包含有关LightOJ问题的教程的存储库
leetcode 2 和 c 动态规划 动态规划相关问题的解答。 这些问题来自各种在线评委,包括 、 、 等。 解决方案是用 C++ 编码的。 —— —— —— —— —— —— —— —— —— —— —— —— ...——
已解决的编程问题 Online Judges 这个存储库包含我解决的各种在线法官的编程问题的解决方案,即 UVa、Topcoder、Codeforces、Hackerrank、LightOj、Spoj、Project Euler 等。
光OJ 收集我在发现的一些问题的解决方案
race_words = [“后缀数组”,“前缀特里”,“动态编程”,“竞赛”,“ codeforces”,“编程”,“竞争性编程”,“算法”,“数据结构”,“ codeforces”,“ light oj”,“ lightoj”,“ spoj”,“堆栈”,...
这是乔杜里医学博士。 伊斯玛姆·拉赫曼(Ishmam Rahman) :closed_mailbox_with_raised_flag: 联络我: ... LightOJ: ://lightoj.com/user/ishmam64 脸书: : 目标:使自己在新技术的海洋中立足,在这里我可
描述在这里,您可以从uva,lightoj,spoj,timus等不同的在线法官那里找到我解决的问题。
这个仓库是关于什么的 创建该存储库是为了组织与数据结构和算法有关的问题的解决方案。 并且,如果可能的话,为学习与数据结构和算法有关的各种概念提供一种更简单的方法。 以下评委使用的问题 ...
开心农场java源码AA Noman Ansary 你好呀! 我的名字是AA Noman Ansary 。 但我更喜欢被称为Showrav...问题解决:LightOJ。 代码部队。 蒂姆斯。 紫外线。 成就 以下是我的一些显著成就: BRAC 大学副校长证书。 (2019)
测试程序TestProgram 是针对竞争性编程程序(即 Codeforces、lightOJ、OmegaUp 等)的专用测试工具。 当我们解决问题时,我们必须非常小心,并致力于解决所有可能的情况。 我们的解决方案在登顶前正确解决的测试用例...
problemSolving