第十四个目标(dp + 树状数组 + 线段树)

Problem 2236 第十四个目标

Accept: 17 Submit: 35 Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

目暮警官、妃英里、阿笠博士等人接连遭到不明身份之人的暗算，柯南追踪伤害阿笠博士的凶手，根据几起案件现场留下的线索发现凶手按照扑克牌的顺序行凶。在经过一系列的推理后，柯南发现受害者的名字均包含扑克牌的数值，且扑克牌的大小是严格递增的，此外遇害者与毛利小五郎有关。

为了避免下一个遇害者的出现，柯南将可能遭到暗算的人中的数字按关联程度排列了出来，即顺序不可改变。柯南需要知道共有多少种可能结果，满足受害人名字出现的数字严格递增，但是他柯南要找出关键的证据所在，所以这个任务就交给你了。

(如果你看不懂上面在说什么，这题是求一个数列中严格递增子序列的个数。比如数列(1,3,2)的严格递增子序列有(1)、(3)、(2)、(1,3)、(1,2)，共5个。长得一样的但是位置不同的算不同的子序列，比如数列(3,3)的答案是2。)

Input

多组数据(<=10)，处理到EOF。

第一行输入正整数N(N≤100 000)，表示共有N个人。

第二行共有N个整数Ai(1≤Ai≤10^9)，表示第i个人名字中的数字。

Output

每组数据输出一个整数，表示所有可能的结果。由于结果可能较大，对1 000 000 007取模后输出。

Sample Input

3 1 3 2

Sample Output

Source

福州大学第十三届程序设计竞赛

题解：dp的思路很好想，dp[i]代表i结尾的递增序列的个数；

dp[i] = 1 + sum{dp[j]}(j < i, a[j] < a[i]);

看到sum(dp[j]),a[]j < a[i]，我们很容易想到树状数组；由于数字过大，那么我们离散化下就好了；

代码：

#include<iostream>

#include<cmath>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<queue>

#include<vector>

using namespace std;

const int MAXN = ;

int dp[MAXN];

int a[MAXN], b[MAXN];

int tree[MAXN];

typedef long long LL;

const int MOD = 1e9 + ;

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

void update(int i, int x){

    while(i < MAXN){

        tree[i] += x;

        tree[i] %= MOD;

        i += lowbit(i);

    }

}

int sum(int i){

    int ans = ;

    while(i > ){

        ans += tree[i];

        ans %= MOD;

        i -= lowbit(i);

    }

    return ans;

}

int main()

{

    int n;

    while (~scanf("%d", &n)) {

        for (int i = ; i < n; i++) {

            scanf("%d", a + i);

            b[i] = a[i];

        }

        sort(a, a + n);

        memset(dp, , sizeof(dp));

        memset(tree, , sizeof(tree));

        LL ans = ;

        int k = unique(a, a + n) - a;

        for (int i = ; i < n; i++) {

            int p = lower_bound(a, a + k, b[i]) - a + ;

            dp[i] = sum(p - ) + ;

            update(p, dp[i]);

        }

        for(int i = ; i < n; i++){

            ans += dp[i];

            ans %= MOD;

        }

        printf("%lld\n", ans % MOD);

    }

    return ;

}

比赛的时候刚开始想着用优先队列优化的，没什么用，还是超时；

代码：

#include<iostream>

#include<cmath>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<queue>

using namespace std;

const int MAXN = ;

int dp[MAXN];

int a[MAXN];

int tree[MAXN];

typedef long long LL;

const int MOD = 1e9 + ;

struct Node{

    int v,p;

    friend bool operator < (Node a, Node b){

        return a.v > b.v;

    }

};

int main()

{

    int n;

    while (~scanf("%d", &n)) {

        for (int i = ; i <= n; i++) {

            scanf("%d", a + i);

        }

        memset(dp, , sizeof(dp));

        LL ans = ;

        priority_queue<Node>Q, Q1;

        Node x;

        for (int i = ; i <= n; i++) {

            dp[i] = ;

            x.v = a[i];x.p = i;

            Q.push(x);

            while(Q.top().v < a[i]){

                dp[i] = (dp[i] + dp[Q.top().p])%MOD;

                Q1.push(Q.top());

                Q.pop();

            }

            while(!Q1.empty()){

                Q.push(Q1.top());

                Q1.pop();

            }

        }

        for(int i = ; i <= n; i++){

            ans += dp[i];

            ans %= MOD;

        }

        printf("%lld\n", ans % MOD);

    }

    return ;

}

线段树又写了下，发现还是用二分好，用了结构体各种错。。。

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll root<<1

#define rr root<<1|1

#define lson ll,l,mid

#define rson rr,mid+1,r

const int MOD = 1e9 + ;

const int MAXN = ;

typedef long long LL;

LL tree[MAXN << ];

LL dp[MAXN];

void pushup(int root){

    tree[root] = (tree[ll] + tree[rr]) % MOD;

}

void update(int root, int l, int r, int a, int b){

    int mid = (l + r) >> ;

    if(a == l && a == r){

        tree[root] += b;

        return;

    }

    if(mid >= a)

        update(lson, a, b);

    else

        update(rson, a, b);

    pushup(root);

}

LL ans;

void query(int root, int l, int r, int a, int b){

    int mid = (l + r) >> ;

    if(l >= a && r <= b){

        ans += tree[root];

        ans %= MOD;

        return;

    }

    LL ans = ;

    if(mid >= a)

        query(lson, a, b);

    if(mid < b)

        query(rson, a, b);

    return ;

}

int a[MAXN], b[MAXN];

int main(){

    int N;

    while(~scanf("%d", &N)){

        for (int i = ; i < N; i++) {

            scanf("%d", a + i);

            b[i] = a[i];

        }

        sort(a, a + N);

        memset(tree, , sizeof(tree));

        memset(dp, , sizeof(dp));

        int k = unique(a, a + N) - a;

        for(int i = ; i < N; i++){

            int p = lower_bound(a, a + k, b[i]) - a + ;

            ans = ;

            query(, , N + , , p - );

            dp[i] = ans + ;

            dp[i] %= MOD;

            update(, , N + , p, dp[i]);

        }

        printf("%lld\n", tree[] % MOD);

    }

    return ;

}

秒客网