挑战程序竞赛系列（37）：3.4利用数据结构高效求解

用户1147447

发布于 2019-05-26 09:40:37

3830

发布于 2019-05-26 09:40:37

文章被收录于专栏：机器学习入门机器学习入门

挑战程序竞赛系列（37）：3.4利用数据结构高效求解

详细代码可以fork下Github上leetcode项目，不定期更新。

练习题如下：

POJ 1769: Minimizing Maximizer

思路：经历了一些波折，首先是考虑DP，DPj，表示在第j个位置所需要的最短的子序列的长度。

更新式还是比较好推的，因为DPj表示到第j个位置所需要的最短子序列长度，那么到下一个位置时，此时的区间长度为si, ti，那么，只要DPj在si和ti之间就可以更新为： DP[ti] =min{DP[ti], DP[j] + 1}, j >= si && j <= ti

物理含义：只要在区间内，1, j能够被排序，那么只要后续区间包含了j，那么自然也就能更新至1,ti.

初始代码如下：

    void solve() {
        int N = ni();
        int M = ni();
        Pair[] ps = new Pair[M];
        for (int i = 0; i < M; ++i){
            ps[i] = new Pair(ni(), ni());
        }

        int[] dp = new int[N + 16];
        Arrays.fill(dp, INF);
        dp[1] = 0;

        for (int i = 0; i < M; ++i){
            int s = ps[i].s;
            int e = ps[i].e;
            for (int j = 1; j <= N; ++j){
                if (j >= s && j <= e){
                    dp[e] = Math.min(dp[e], dp[j] + 1);
                }
            }
        }

        out.println(dp[ps[M - 1].e]);
    }

可以观察下for循环中求最小值，此处可以用RMQ替代，无非就是求区间s,e中的最小值，这样时间复杂度降为O(nlogn)O(n\log n)

哈哈，今天更新了最新的算法模版，拿来POJ实测一波，支持codeforce，uva，aoj哟，代码如下：

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
    String INPUT = "./data/judge/201708/P1769.txt";

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    class Pair{
        int s;
        int e;
        public Pair(int s, int e){
            this.s = s;
            this.e = e;
        }

        @Override
        public String toString() {
            return s + " " + e;
        }
    }

    static final int MAX_N = 50000 + 16;
    static final int SIZE = (1 << 18) + 1;
    static final int INF = 1 << 29;

    int[] dat = new int[SIZE];

    int[] dp;

    void solve() {
        int N = ni();
        int M = ni();
        Pair[] ps = new Pair[M];
        for (int i = 0; i < M; ++i){
            ps[i] = new Pair(ni(), ni());
        }

        dp = new int[MAX_N];
        Arrays.fill(dp, INF);
        init(N);

        dp[1] = 0;
        update (1, 0);
        for (int i = 0; i < M; ++i){
            int s = ps[i].s;
            int e = ps[i].e;
            int min = Math.min(dp[e],query(0, s, e + 1, 0, n_) + 1);
            dp[e] = min;
            update(e, min);
        }

        out.println(dp[N]);
    }

    /*********************以下是RMQ的实现*********************/

    /**
     * [L, r)
     * @param k
     * @param l
     * @param r
     */

    int n_;

    public void init(int N){
        n_ = 1;
        while (n_ < N) n_ *= 2;
        for (int i = 0; i < 2 * n_ - 1; ++i) dat[i] = INF;
    }

    public void update(int k, int val){
        k += (n_ - 1);
        dat[k] = val;
        while (k > 0){
            k = (k - 1) / 2;
            dat[k] = Math.min(dat[2 * k + 1], dat[k * 2 + 2]);
        }
    }

    public int query(int k, int i, int j, int l, int r){
        if (j <= l || i >= r) return INF;
        else if (i <= l && j >= r){
            return dat[k];
        }
        else{
            int lch = 2 * k + 1;
            int rch = 2 * k + 2;
            int mid = (l + r) / 2;
            int lf = query(lch, i, j, l, mid);
            int rt = query(rch, i, j, mid, r);
            return Math.min(lf, rt);
        }
    }



    FastScanner in;
    PrintWriter out;

    void run() throws IOException {
        boolean oj;
        try {
            oj = !System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
        } catch (Exception e) {
            oj = System.getProperty("ONLINE_JUDGE") != null;
        }

        InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
        in = new FastScanner(is);
        out = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if (!oj) {
            System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
        }
    }

    public boolean more() {
        return in.hasNext();
    }

    public int ni() {
        return in.nextInt();
    }

    public long nl() {
        return in.nextLong();
    }

    public double nd() {
        return in.nextDouble();
    }

    public String ns() {
        return in.nextString();
    }

    public char nc() {
        return in.nextChar();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        boolean hasNext;

        public FastScanner(InputStream is) throws IOException {
            br = new BufferedReader(new InputStreamReader(is));
            hasNext = true;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    hasNext = false;
                    return "##";
                }
            }
            return st.nextToken();
        }

        String next = null;

        public boolean hasNext() {
            next = nextToken();
            return hasNext;
        }

        public int nextInt() {
            if (next == null) {
                hasNext();
            }
            String more = next;
            next = null;
            return Integer.parseInt(more);
        }

        public long nextLong() {
            if (next == null) {
                hasNext();
            }
            String more = next;
            next = null;
            return Long.parseLong(more);
        }

        public double nextDouble() {
            if (next == null) {
                hasNext();
            }
            String more = next;
            next = null;
            return Double.parseDouble(more);
        }

        public String nextString() {
            if (next == null) {
                hasNext();
            }
            String more = next;
            next = null;
            return more;
        }

        public char nextChar() {
            if (next == null) {
                hasNext();
            }
            String more = next;
            next = null;
            return more.charAt(0);
        }
    }
}

RMQ的实现有一个坑点，其实和《挑战》P188的递归实现还是有一些出入的，原因在与update更新是利用完全二叉树的性质来做的，而如果单纯的递归实现，如果不控制右边界r，那么会导致不匹配，找了很久错误都没找到。

所以init()中，把N转为最近的2次幂，这样一来，在query查询时，可以以完全二叉树的方式来遍历，这样就和update匹配了。

POJ 3171: Cleaning Shifts

感觉比上一题简单，可以用DIJKSTRA，建立点与边的关系，也可以用DP，同理DPj表示在第j个位置，所需要消耗的最小代价，把上题的dpj + 1，改成dpj + c，其他的都不变。传统DP超时，所以还是用RMQ吧！

代码如下：

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{

    String INPUT = "./data/judge/201708/P3171.txt";

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    static final int INF = 1 << 29;

    class Cow implements Comparable<Cow>{
        int s;
        int e;
        int c;
        public Cow(int s, int e, int c){
            this.s = s;
            this.e = e;
            this.c = c;
        }
        @Override
        public int compareTo(Cow that) {
            return this.e == that.e ? this.s - that.s : this.e - that.e;
        }
    }

    void solve() {
        int N = ni();
        int M = ni();
        int E = ni();

        Cow[] cows = new Cow[N];
        for (int i = 0; i < N; ++i){
            cows[i] = new Cow(ni(), ni(), ni());
        }

        int[] dp = new int[E + 16];
        Arrays.fill(dp, INF);
        dp[M] = 0;

        init(E);
        Arrays.sort(cows);

        update(M, 0);

        for (int i = 0; i < N; ++i){
            int s = cows[i].s;
            int e = cows[i].e;
            s = s == 0 ? 0 : s - 1;
            int min = Math.min(dp[e], query(0, s, e, 0, n_) + cows[i].c);
            dp[e] = min;
            update(e, min);
        }

        out.println(dp[E] >= INF ? -1 : dp[E]);
    }

    /*****************RMQ*******************/

    static final int MAX_N = (1 << 18) - 1;
    int n_;

    int[] dat = new int[MAX_N];

    public void init(int N){
        n_ = 1;
        while (n_ < N) n_ *= 2;
        for (int i = 0; i < 2 * n_ - 1; ++i) dat[i] = INF;
    }

    public void update(int k, int val){
        k += (n_ - 1);
        dat[k] = val;
        while (k > 0){
            k = (k - 1) / 2;
            dat[k] = Math.min(dat[2 * k + 1], dat[2 * k + 2]);
        }
    }

    public int query(int k, int i, int j, int l, int r){
        if (j <= l || i >= r) return INF;
        else if (i <= l && j >= r) return dat[k];
        else{
            int lch = 2 * k + 1;
            int rch = 2 * k + 2;
            int mid = (l + r) / 2;
            int lf = query(lch, i, j, l, mid);
            int rt = query(rch, i, j, mid, r);
            return Math.min(lf, rt);
        }
    }


    FastScanner in;
    PrintWriter out;

    void run() throws IOException {
        boolean oj;
        try {
            oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
        } catch (Exception e) {
            oj = System.getProperty("ONLINE_JUDGE") != null;
        }

        InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
        in = new FastScanner(is);
        out = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if (!oj){
            System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
        }
    }

    public boolean more(){
        return in.hasNext();
    }

    public int ni(){
        return in.nextInt();
    }

    public long nl(){
        return in.nextLong();
    }

    public double nd(){
        return in.nextDouble();
    }

    public String ns(){
        return in.nextString();
    }

    public char nc(){
        return in.nextChar();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        boolean hasNext;

        public FastScanner(InputStream is) throws IOException {
            br = new BufferedReader(new InputStreamReader(is));
            hasNext = true;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    hasNext = false;
                    return "##";
                }
            }
            return st.nextToken();
        }

        String next = null;
        public boolean hasNext(){
            next = nextToken();
            return hasNext;
        }

        public int nextInt() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Integer.parseInt(more);
        }

        public long nextLong() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Long.parseLong(more);
        }

        public double nextDouble() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Double.parseDouble(more);
        }

        public String nextString(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more;
        }

        public char nextChar(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more.charAt(0);
        }
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017年08月25日，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

二叉树

编程算法

登录后参与评论

0 条评论

热度

挑战程序竞赛系列（37）：3.4利用数据结构高效求解

挑战程序竞赛系列（37）：3.4利用数据结构高效求解

挑战程序竞赛系列（37）：3.4利用数据结构高效求解

POJ 1769: Minimizing Maximizer

POJ 3171: Cleaning Shifts

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐