`

hdu 2227 Find the nondecreasing subsequences(DP+树状数组+离散化)

阅读更多

Find the nondecreasing subsequences

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 503    Accepted Submission(s): 192

Problem Description
How many nondecreasing subsequences can you find in the sequence S = {s1, s2, s3, ...., sn} ? For example, we assume that S = {1, 2, 3}, and you can find seven nondecreasing subsequences, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}.

 

Input
The input consists of multiple test cases. Each case begins with a line containing a positive integer n that is the length of the sequence S, the next line contains n integers {s1, s2, s3, ...., sn}, 1 <= n <= 100000, 0 <= si <= 2^31.

 

Output
For each test case, output one line containing the number of nondecreasing subsequences you can find from the sequence S, the answer should % 1000000007.

 

Sample Input
3 1 2 3

 

Sample Output
7
         
          题目大意:给你一个串,求这个串中不递减的子串有多少个?初一看,完全想不到会是用树状数组,但是他就是这么神奇,不递减就想到逆序数,逆序数又想到了树状数组,居然是用他。他是求子串有多少个,又要用到DP,这里DP就是用树状数组慢慢推上去,最后是注意是求和会溢出,记得%1000000007。
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;

struct node
{
    int val, id;
}a[100005];

bool cmp(node a, node b)
{
    return a.val < b.val;
}

int b[100005], c[100005], s[100005], n;

int lowbit(int i)
{
    return i&(-i);
}

void update(int i, int x)
{
    while(i <= n)
    {
        s[i] += x;
        if(s[i] >= 1000000007)
            s[i] %= 1000000007;
        i += lowbit(i);
    }
}

int sum(int i)
{
    int sum = 0;
    while(i > 0)
    {
        sum += s[i];
        if(sum >= 1000000007)
            sum %= 1000000007;
        i -= lowbit(i);
    }
    return sum;
}

int main()
{
    int i, res;
    while(scanf("%d", &n) != EOF)
    {
        memset(b, 0, sizeof(b));
        memset(s, 0, sizeof(s));
        for(i = 1; i <= n; i++)
        {
            scanf("%d", &a[i].val);
            a[i].id = i;
        }
        sort(a+1, a+n+1, cmp);
        b[a[1].id] = 1;
        for(i = 2; i <= n; i++)
        {
            if(a[i].val != a[i-1].val)
                b[a[i].id] = i;
            else b[a[i].id] = b[a[i-1].id];
        }
        res = 0;
        for(i = 1; i <= n; i++)
        {
            c[i] = sum(b[i]);
            update(b[i], c[i]+1);
        }
        printf("%d\n", sum(n));
    }

    return 0;
}
 
0
3
分享到:
评论

相关推荐

    树状数组(Binary Indexed Tree)

    **树状数组**(Binary Indexed Tree, BIT),又称**费尼克树**(Fenwick Tree),是一种特殊的数据结构,它能高效地完成对数组元素的累加查询和更新操作。相较于其他数据结构如线段树,树状数组在实现上更为简洁,...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    HDU+2000-2099+解题报告

    6. **数据结构**:堆(大顶堆、小顶堆)、平衡二叉搜索树(AVL、红黑树)、树状数组、 Fenwick Tree(二分索引树)等。 7. **组合数学**:排列组合、鸽巢原理、容斥原理、卡特兰数、斯特林数等。 8. **概率统计**...

    背包DP与树形DP

    ### 背包DP与树形DP:深入解析与实战应用 #### 背包DP:从基础到进阶 **动态规划(DP)**是一种解决具有重叠子问题和最优子结构特征问题的有效方法,而**背包问题**是动态规划中最经典的应用之一,主要分为01背包、...

    HDU ACM as easy as a+b

    - **变量声明与初始化**:例如 `int n, m, j, i, k, l;` 和 `long int a[1000];` 分别声明了多个整型变量和一个长度为1000的长整型数组。 - **循环结构**:使用 `for` 循环来实现重复操作,例如 `for(k=0;k;k++)` 和...

    hdu 1695 GCD(欧拉函数+容斥原理).docx

    "hdu 1695 GCD(欧拉函数+容斥原理)" 题目大意是:给定 a, b, c, d, k,找到一队 x, y,满足 g(x, y) = k,且 x ∈ [1, b], y ∈ [1, d],问有多少对符合要求的 (x, y)。 思路是:gcd(x, y) == k 解释 x, y 都能...

    HDU DP 题集

    动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...

    ACM hdu 线段树题目+源代码

    线段树是一种树形结构,它将一个数组分割成多个小 区间,每个区间对应树上的一个节点。线段树的每个节点都包含了该节点对应的区间信息。 线段树的主要应用 线段树的主要应用是解决区间问题,例如区间和、区间...

    hdu 3341(ac自动机+状态压缩)

    hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...

    HDU DP题解

    HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高

    hdu 1257 最低拦截系统 lis

    - **初始化**:对于每个元素,最短的递增子序列长度至少为1,即`dp[i] = 1`。 - **求解结果**:遍历整个数组,取`dp`数组中的最大值即可得到最长递增子序列的长度。 ### 代码实现分析 提供的代码实现了上述思路: ...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    HDU+2000-2099+解题报告.zip

    《杭电OnlineJudge 2000-2099解题报告》是针对杭州电子科技大学(HDU)在线评测系统(OnlineJudge)中2000至2099题目的详细解答集锦,主要涵盖了算法分析、编程技巧以及问题解决策略等内容。这份解题报告以CHM...

    hdu 300+ AC 代码

    线段树在处理动态区间问题时非常有效,如在数组上进行区间加法、区间求和等操作。理解和熟练运用线段树是解决复杂数据结构题目的关键。 3. **字符串处理**:字符串是编程中常见的数据类型,用于处理文本信息。字符...

    vc2019中 源文件<bits/stdc++.h>无法打开

    在VC2019中,当你遇到"源文件&lt;bits/stdc++.h&gt;无法打开"的问题时,这通常意味着你试图在你的C++项目中使用一个预编译头文件,但是这个文件在标准库中并不存在。`&lt;bits/stdc++.h&gt;`是GCC编译器中的一个非标准头文件,它...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    hdu.rar_hdu

    3. **数据结构**:数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图(邻接矩阵、邻接表、最小生成树、拓扑排序等)。 4. **字符串处理**:KMP算法、Manacher's Algorithm、Rabin-Karp算法等。 5. **...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    DP.rar_DP_hdu_动态规划_动态规划 C++

    标题中的“DP.rar”表明这是一个关于动态规划的资料压缩包,而“DP_hdu”暗示了这些题目可能来自杭州电子科技大学(HDU)的在线编程平台。动态规划通常用于解决那些可以通过子问题的最优解来构建原问题最优解的问题...

    HDU图论题目分类

    HDU图论题目分类 HDU图论题目分类是指在杭州电子科技大学(Hangzhou Dianzi University)的判题平台HDU OJ(Online Judge)上收录的一系列图论题目的分类。本分类涵盖了图论领域的多种类型的题目,涉及到图论的基本...

Global site tag (gtag.js) - Google Analytics