Man Down 解题报告(hdu3016 动态规划 线段树 排序)

http://acm.hdu.edu.cn/showproblem.php?pid=3016

算法设计

拿到题二话不说,先把这些木板按照其高从小到大排个序,然后我们给木板从下到上从1开始递增编号(我们认为最下面的地板编号为0),通过这样的一个步骤,显然,越高的木板序号越大。

根据题意,如果人在一个木板上,他只可以从这个木板的左端或者右端垂直下落。我们定义 d[i] 为当这个人到达第 i 个板的时候最大生命值。如果我们知道 d[i] 的值,我们就可以推出其左端或者右端下落到的板子相应的值。(d[j] = d[i] + 跳到 j 板上生命值的变化量)。这样,我们可以从上往下递推的求解。

但是我们如何知道这个人他在左端或者右端下落会落到哪里呢?我们可以对 x 轴根据点建立一棵线段树,然后从下往上根据木板对这个 x 轴“染色”(即对木板所覆盖的地方标记上自己的序号),这样的话,在往上推进的过程中,很方便就能求出一个木板左右端跳下去会跳到哪个板上。

示例代码

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 110000, L = 110000, INF = 0x7fffffff;

int n;

struct a_d {
    int h, l, r, v;
    int ld, rd; // left down to 
} a[N];

inline bool cmp(a_d a, a_d b) {
    return a.h < b.h;
}

struct node {
    int l, r;
    int f;
    node *lc, *rc;
} mem[2 * L];
node *memp;
node *root;

node *init(int l, int r) {
    node *p = memp++;
    p->l = l;
    p->r = r;
    p->f = 0;
    if (l == r) {
        p->lc = p->rc = NULL;
    } else {
        int mid = (l + r) >> 1; 
        p->lc = init(l, mid);
        p->rc = init(mid + 1, r);
    }
    return p;
}

inline void push_down(node *p) {
    if (p->f) {
        p->lc->f = p->f;
        p->rc->f = p->f;
        p->f = 0;
    }
}

void change(node *p, int l, int r, int f) {
    if (l <= p->l && p->r <= r) {
        p->f = f;
        return;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    if (l <= mid) change(p->lc, l, r, f);
    if (mid < r) change(p->rc, l, r, f);
}

int query(node *p, int i) {
    if (i == p->l && p->r == i) {
        return p->f;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    if (i <= mid) return query(p->lc, i);
    return query(p->rc, i);
}

int d[N]; 

inline int max(int a, int b) {
    if (a > b) return a; else return b;
}

int main() {
//  freopen("input.txt", "r", stdin);

    while(scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; ++i) scanf("%d%d%d%d", &a[i].h, &a[i].l, &a[i].r, &a[i].v);
        a[0].v = 0;

        std::sort(a + 1, a + n + 1, cmp);
//      
//      for (int i = 1; i <= n; ++i) printf("%d %d %d\n", i, a[i].l, a[i].r); printf("\n");

        memp = mem;
        root = init(0, 100010);
        for (int i = 1; i <= n; ++i) { 
//          printf("%d %d %d\n", i, a[i].l, a[i].r);
            a[i].ld = query(root, a[i].l); // 注意这里不 +1 -1
            a[i].rd = query(root, a[i].r);
            change(root, a[i].l, a[i].r, i);
        }
//      
//      for (int i = 1; i <= n; ++i) printf("%d %d %d\n", i, a[i].ld, a[i].rd);

        for (int i = 0; i <= n; ++i) d[i] = -INF;
        d[n] = 100 + a[n].v;
        for (int i = n; i; --i) {
            if (d[i] <= 0) continue;
            d[a[i].ld] = max(d[a[i].ld], d[i] + a[a[i].ld].v);
            d[a[i].rd] = max(d[a[i].rd], d[i] + a[a[i].rd].v);
        }

        if (d[0] > 0) printf("%d\n", d[0]); else printf("-1\n");
    }

    return 0;
}

HH 的项链 解题报告(SDOI 2009 线段树 排序 离线处理)

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH 不断地收集新的贝壳,因此他的项链变得越来越长。

有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?

这个问题很难回答。。。因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。

输入

第一行:一个整数N,表示项链的长度。

第二行:N个整数,表示依次表示项链中贝壳的编号(编号为0到1000000之间的整数)。

第三行:一个整数M,表示HH询问的个数。

接下来M行:每行两个整数,L和R(1 ≤ L ≤ R ≤ N),表示询问的区间。

N ≤ 50000,M ≤ 200000。

输出

M行,每行一个整数,依次表示询问对应的答案。

样例输入

6
1 2 3 4 3 5
3
1 2
3 5
2 6

样例输出

2
2
4

来源

SDOI 2009

在线评测

lydsy

vjudge

算法设计

看到题目,首先想了想所学的数据结构,当前还没有如此高级的数据结构可以求任意的一个区间内有多少种数字。那么我们试试能不能在确定一个端点的前提下,通过简单的数据结构得到结果。

这道题目我们需要离线处理,将所有的查询根据右节点从小到大排序,使其变得有序后进行操作。

我们定义一个变量 k 为当前推进(或者说枚举)到的右节点,定义一棵线段树,第 j 个节点的含义为 j-k 内不同的数字个数

我们定义一个数组 last 数组,第 i 个元素为 第 i 个贝壳序号 在 贝壳序列中 上一次出现的位置。

我们可以发现,如果我们推进到了一个新的 k,很明显 1 ~ last[k] 到 k 这些段中一定是存在 第 k 个贝壳序号,而在 last[k] + 1 ~ k 到 k 这些段中是不存在的。那反映到线段树中 last[i] + 1 ~ k 所有节点都应该 + 1。

没听懂?没关系,可以看看下面的代码。

示例代码

#include <cstdio>
#include <cstring>
#include <algorithm>

//using namespace std;

const int N = 55000, M = 220000, MAX = 1100000;

int n, m, a[N];

int last[N];
int idx[MAX]; // 本来是 index 但是与头文件中的函数冲突了 

struct q_d {
    int l, r, id;
} q[M];

int result[M];

inline bool cmp(q_d a, q_d b) {
    return a.r < b.r;
}

struct node {
    int l, r;
    int f;
    node *lc, *rc;
} mem[2 * N];
node *memp;
node *root;

inline void push_down(node *p) {
    if (p->f) {
        p->lc->f += p->f;
        p->rc->f += p->f;
        p->f = 0;
    }
}

node *init(int l, int r) {
    node *p = memp++;
    p->l = l;
    p->r = r;
    p->f = 0;
    if (l == r) {
        p->lc = p->rc = NULL;
    } else {
        int mid = (l + r) >> 1;
        p->lc = init(l, mid);
        p->rc = init(mid + 1, r); 
    }

    return p;
}

void change(node *p, int l, int r) {
    if (l <= p->l && p->r <= r) {
        ++p->f;
        return;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    if (l <= mid) change(p->lc, l, r);
    if (mid < r) change(p->rc, l, r);
} 

int query(node *p, int i) {
    if (p->l == p->r) {
        return p->f;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    if (i <= mid) return query(p->lc, i);
    return query(p->rc, i);
}

int main() {
//  freopen("input.txt", "r", stdin);

    scanf("%d", &n);
    memset(idx, 0, sizeof idx);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        last[i] = idx[a[i]];
        idx[a[i]] = i;
    }

    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    std::sort(q + 1, q + m + 1, cmp);
//  
//  for (int i = 1; i <= m; ++i) printf("%d %d\n", q[i].l, q[i].r);

    int j = 1;
    memp = mem;
    root = init(1, n);
    for (int i = 1; i <= n; ++i) {
        change(root, last[i] + 1, i); 
        for (; q[j].r == i && j <= m; ++j) {
            result[q[j].id] = query(root, q[j].l);
        }
    }

    for(int i = 1; i <= m; ++i) printf("%d\n", result[i]);

    return 0;
}

The Bakery 解题报告(cf833b dp 带优化的dp 线段树)

http://codeforces.com/contest/833/problem/B

NOTICE

推荐在写这道题前看看 HH 的项链 解题报告(SDOI 2009 线段树 排序 离线处理)

算法设计

拿到题,3分钟,这是一道动态规划。写码,调试,提交,一气呵成,最后发现在第4个点超时。转过头来看,发现在处理每一个状态的时候套着一个循环,导致整体算法复杂度 O(n ^ 3) 遂放弃。

最近学习了线段树,然后再看这道题,发现了这道题在求不同数字的个数的时候进行了很多不必要的重复运算,可以用线段树解决。

由于本人的描述实在不行,具体解决方案请直接看下面代码以及其注释,先粗略看一遍全局变量的定义,然后再看一下main函数。

配合这张图食用更佳。

示例代码

#include <cstdio>
#include <cstring>

const int N = 38500; // 35000 * 1.1 

int n, k, a[N]; // 题目中提供的数据 

int last[N]; // 记录该位置的数上一次出现的位置,last[i] 代表 a[i] 位置上的数在 a 数组中上一次出现的位置,如果没有出现过,则为 0 
int index[N]; // 用于辅助建立 last 数组 

int d[N]; // 动态规划中用于保留结果的数组, d[i] 代表在一次切割中(阶段),最后一个切割点(或者说是最后一个箱子装的最后一个蛋糕的坐标)的结果 

struct node {
    int l, r;
    int f;
    int max;
    node *lc, *rc;
} mem[2 * N];
node *memp;
node *root; // 线段树中第 i 个位置的数 为 上一个阶段 d[i] 以及 i + 1 ~ j 中不同数字的个数 的和,其中 j 为当前推进到的位置,详见下方解释 

inline void push_down(node *p) {
    if (p->f) {
        p->lc->max += p->f;
        p->lc->f += p->f; // mistake: 就像傻子一般,线段树这里给写错了 
        p->rc->max += p->f;
        p->rc->f += p->f;
        p->f = 0;
    }
}

inline void pull_up(node *p) {
    if (p->lc->max > p->rc->max) p->max = p->lc->max; else p->max = p->rc->max;
}

node *init(int a[], int l, int r) {
    node *p = memp++;
    p->l = l;
    p->r = r;
    p->f = 0;
    if (l == r) {
        p->lc = p->rc = NULL;
        p->max = a[l];
    } else {
        int mid = (l + r) >> 1;
//      printf("%d %d %d\n", l, mid, r);
        p->lc = init(a, l, mid);
        p->rc = init(a, mid + 1, r);
        pull_up(p);
    }
    return p;
}

void change(node *p, int l, int r) {
    if (l <= p->l && p->r <= r) {
        ++p->max;
        ++p->f;
        return;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    if (l <= mid) change(p->lc, l, r);
    if (mid < r) change(p->rc, l, r);
    pull_up(p);
}

int query(node *p, int l, int r) {
    if (l <= p->l && p->r <= r) {
        return p->max;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    int max = 0, tmp;
    if (l <= mid) {
        max = query(p->lc, l, r);
    }
    if (mid < r) {
        tmp = query(p->rc, l, r);
        if (tmp > max) max = tmp;
    }
    pull_up(p); // mistake:这里的pull_up是不可或缺的 

    return max;
}
//
//void debug2() {
//  for (int i = 1; i <= n; ++i) printf("%d ", last[i]);
//  printf("\n\n");
//}
//
//void debug1() {
//  for (int i = 0; i <= n; ++i) printf("%d ", d[i]);
//  printf("\n");
//} 

int main() {
//  freopen("input.txt", "r", stdin);

    scanf("%d%d", &n, &k);
    memset(index, 0, sizeof index);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        last[i] = index[a[i]]; // 读取输入的过程中同时填充一下 last 数组,last 数组的含义见上定义 
        index[a[i]] = i;
    }
//  
//  debug2();

    // 动态规划,为了能够对动态规划中的一个阶段中的不同状态下的求解能够快速进行,我们使用了递推,这样求解的顺序可以利用线段树进行优化 
    memset(d, 0, sizeof d); // 不难发现最开始的结果都是 0 的 
    for (int i = 1; i <= k; ++i) { // 阶段,即切割或者说是箱子的个数 
        memp = mem;
        root = init(d, 0, n); // 线段树是可以从 0 开始建立的,详见下方解释 
        for (int j = i; j <= n; ++j) { // 枚举当前阶段切割点的位置 
            // 诚然,我们对于每一个切割点而言,我们都可以跑一次如下的循环 
            /* 
            int max = 0, tmp;
            for (int k = i - 1; k <= j - 1; ++k) { // 很明显 i - 1 之前的是不可能满足题意的 
                tmp = last_d[k] + different_num_between(k, j);
                if (tmp > max) max = tmp;
            }
            */
            // 但是这样太慢了,我们发现,计算从 k 到 j 的有多少个不同的数字这个函数被调用了很多遍,并且发现貌似每次都进行了许多无用的计算
            // 我们建立一棵线段树,定义为当推进到 j 位置的时候,线段树中第 k 个数为从 k + 1(加一是为了初始化方便) 到 j 中不同数字的个数
            // 我们可以发现,last[j] + 1 到 j 中间是没有 a[j] 这个数的(一句废话)
            // 那也就是说,如果我们的进度推进到了 j 的话,对于所有的 在 last[j] + 1 ~ j 中的位置到 j 的不同数字种类应该会多出一个 j ,反映到数量上,就是个数 +1 
            // 映射到线段树的时候别忘了位置 -1 
            //  
            // 我们还可以发现,如果说按照上述定义,求最大值仍然需要扫描整个线段树,因为在原始的线段树上我们还需要增加上一个阶段的结果
            // 那么我们索性就在线段初始化的时候,将 d 数组作为线段树最开始的初始化用数组,这样求最大值就可以用线段树舒服的求出来了(当然线段树写错了当我没说) 
            // 
            // 被绕晕了?可以翻上去看看定义那里的注释,并且根据代码理解一下 
            change(root, last[j] + 1 - 1, j - 1); 
            d[j] = query(root, i - 1, j - 1); // mistake: 请注意,这里必须是 i - 1 而不是 i 
        }
//      debug1();
    }
//  
//  // 哦,我的老伙计,这一坨被注释的代码是彻头彻底的错误 
//  int max = 0;
//  for (int i = 1; i <= n; ++i) if (d[i] > max) max = d[i];
//  printf("%d", max);
//  for (int i = 1; i <= n; ++i) printf("%d ", d[i]);
//  printf("%d", d[n]); 

    printf("%d", d[n]);

    return 0;
}