个人空间 - AcWing

nighoc

关注数

粉丝数

阅读量

4630

+关注发消息

离线：4天前

最近来访(31)

353993527

每天少秃一点

嘎嘎嘎嘎嘎嘎嘎

碎银又几两

千初夏

Y_+

祥_4

nooprush

tt2767

愿无忧

slimming

猫猫偷天雷

兜兜里有糖

zsfzmxl

阿景

Isaacs

cow马

小猪软糖z

uhdaskhfd

yok33

题解 AcWing 9. 分组背包问题（java实现，记忆化搜索）

nighoc
1个月前

                import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    final int N = 110;
    int[][] f = new int[N][N];
    int[][] v = new int[N][N];
    int[][] w = new int[N][N];
    int[] s = new int[N];
    int n, m;

    int dp(int i, int j) {
        if(f[i][j] != -1)
            return f[i][j];

        if(i <= 0 || j <= 0)
            return 0;

        for (int k = 0; k <= s[i]; k++) {
            if(v[i][k] <= j)
                f[i][j] = Math.max(f[i][j], dp(i - 1, j - v[i][k]) + w[i][k]);
        }

        return f[i][j];
    }

    public Main() throws IOException {
        String[] line = in.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);

        for (int i = 1; i <= n; i++) {
            s[i] = Integer.parseInt(in.readLine());

            for (int j = 1; j <= s[i]; j++) {
                line = in.readLine().split(" ");
                v[i][j] = Integer.parseInt(line[0]);
                w[i][j] = Integer.parseInt(line[1]);
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j] = -1;
            }
        }
        System.out.println(dp(n, m));

        in.close();
    }

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

}


            

题解 AcWing 4. 多重背包问题 I(java实现，记忆化搜索)

nighoc
1个月前

                import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int n, m;
    final int N = 1010;
    int[] v = new int[N];
    int[] w = new int[N];
    int[] s = new int[N];
    int[][] f = new int[N][N];

    int dp(int i, int j) {
        if(f[i][j] != -1)
            return f[i][j];

        if(i <= 0 || j <= 0)
            return 0;

        for (int k = 0; k <= s[i] && k*v[i] <= j; k++) {
            f[i][j] = Math.max(f[i][j], dp(i - 1, j - k*v[i]) + k * w[i]);
        }

        return f[i][j];
    }

    public Main() throws IOException {
        String[] line = in.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);

        for (int i = 1; i <= n; i++) {
            line = in.readLine().split(" ");
            v[i] = Integer.parseInt(line[0]);
            w[i] = Integer.parseInt(line[1]);
            s[i] = Integer.parseInt(line[2]);

            for (int j = 1; j <= m; j++) {
                f[i][j] = -1;
            }
        }
        System.out.println(dp(n, m));
        in.close();
    }

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

}


            

题解 AcWing 2. 01背包问题(java实现, 记忆化搜索)

nighoc
1个月前

                import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int n, m;
    final int N = 1010;
    int[] v = new int[N];
    int[] w = new int[N];
    int[][] f = new int[N][N];

    int dp(int i, int j) {
        if(f[i][j] != -1)
                return f[i][j];

        if(i <= 0 || j <= 0)
            return 0;

        f[i][j] = dp(i-1, j);
        if(j - v[i] >= 0)
            f[i][j] = Math.max(f[i][j], dp(i - 1, j - v[i]) + w[i]);

        return f[i][j];
    }

    public Main() throws IOException {
        String[] line = in.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);

        for (int i = 1; i <= n; i++) {
            line = in.readLine().split(" ");
            v[i] = Integer.parseInt(line[0]);
            w[i] = Integer.parseInt(line[1]);

            for (int j = 1; j <= m; j++) {
                f[i][j] = -1;
            }
        }
        System.out.println(dp(n, m));

        in.close();
    }

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

}


            

题解 AcWing 4666. 求阶乘( java实现)

nighoc
1个月前

                import java.util.Scanner;

public class Main {

    long get(long n, long p) {
        long res = 0;
        while(n != 0) {
            n /= p;
            res += n;
        }

        return res;
    }

    long bsearch(long l, long r, long x) {
        while(l < r) {
            long mid = (l + r) >> 1;
            if(get(mid, 5) >= x) {
                r = mid;
            }else {
                l = mid + 1;
            }
        }

        return l;
    }



    public Main() {
        Scanner scan = new Scanner(System.in);
        long k = scan.nextLong();
        scan.close();

        long res = bsearch(0, Long.MAX_VALUE, k);
        if(get(res, 5) == k) {
            System.out.println(res);
        }else {
            System.out.println("-1");
        }
    }

    public static void main(String[] args) {
        new Main();
    }

}


            

题解 AcWing 1207. 大臣的旅费( java实现 )

nighoc
2个月前

                import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main { 
    final int N = 100010;
    List<Edge>[] h = new LinkedList[N];
    int[] dist = new int[N];

    void dfs(int u, int father, int distance) {
        dist[u] = distance;
        for (Edge e: h[u]) {
            if(e.id != father)
                dfs(e.id, u, distance + e.w);
        }
    }

    public Main(){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        // 初始化邻接表
        for (int i = 1; i <= n; i++) {
            h[i] = new LinkedList<>();
        }

        for (int i = 0; i < n - 1; i++) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt();

            h[a].add(new Edge(b, c));
            h[b].add(new Edge(a, c));
        }

        dfs(1, -1, 0);

        int u = 1;
        for (int i = 1; i <= n; i++) {
            if(dist[i] > dist[u])
                u = i;
        }

        dfs(u, -1, 0);

        for (int i = 1; i <= n; i++) {
            if(dist[i] > dist[u])
                u = i;
        }

        int s = dist[u];
        System.out.println(10*s + (long)s * (1 + s) / 2);
    }

    public static void main(String[] args){
        new Main();
    }

}

class Edge{
    int id;
    int w;
    public Edge(int id, int w) {
        super();
        this.id = id;
        this.w = w;
    }
}


            

活动打卡代码 AcWing 1233. 全球变暖

nighoc
2个月前

                import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    final int N = 1010;
    char[][] g = new char[N][];
    boolean[][] st = new boolean[N][N];
    int n, total, bound, res = 0;
    Queue<Pos> queue = new LinkedList<>();
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};

    void bfs(int x, int y) {
        queue.add(new Pos(x, y));
        st[x][y] = true;

        bound = total = 0;
        while(!queue.isEmpty()) {
            Pos t = queue.remove();
            total++;

            boolean isBound = false;
            for (int i = 0; i < 4; i++) {
                int a = t.x + dx[i];
                int b = t.y + dy[i];

                if(a < 0 || a >= n || b < 0 || b >= n)
                    continue;

                if(g[a][b] == '.') {
                    isBound = true;
                    continue;
                }

                if(g[a][b] == '#' && !st[a][b]) {
                    st[a][b] = true;
                    queue.add(new Pos(a, b)); 
                }               
            }

            if(isBound)
                bound++;
        }
    }

    public Main() throws IOException {
        n = Integer.parseInt(in.readLine());
        for (int i = 0; i < n; i++) {
            g[i] = in.readLine().toCharArray();
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(g[i][j] == '#' && !st[i][j]) {
                    bfs(i, j);
                    if(total == bound) res++; 
                }
            }
        }
        System.out.println(res);

        in.close();
    }

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

}

class Pos{
    int x;
    int y;

    public Pos(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }
}


            

题解 AcWing 1233. 全球变暖( java实现 )

nighoc
2个月前

                import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    final int N = 1010;
    char[][] g = new char[N][];
    boolean[][] st = new boolean[N][N];
    int n, total, bound, res = 0;
    Queue<Pos> queue = new LinkedList<>();
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};

    void bfs(int x, int y) {
        queue.add(new Pos(x, y));
        st[x][y] = true;

        bound = total = 0;
        while(!queue.isEmpty()) {
            Pos t = queue.remove();
            total++;

            boolean isBound = false;
            for (int i = 0; i < 4; i++) {
                int a = t.x + dx[i];
                int b = t.y + dy[i];

                if(a < 0 || a >= n || b < 0 || b >= n)
                    continue;

                if(g[a][b] == '.') {
                    isBound = true;
                    continue;
                }

                if(g[a][b] == '#' && !st[a][b]) {
                    st[a][b] = true;
                    queue.add(new Pos(a, b)); 
                }               
            }

            if(isBound)
                bound++;
        }
    }

    public Main() throws IOException {
        n = Integer.parseInt(in.readLine());
        for (int i = 0; i < n; i++) {
            g[i] = in.readLine().toCharArray();
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(g[i][j] == '#' && !st[i][j]) {
                    bfs(i, j);
                    if(total == bound) res++; 
                }
            }
        }
        System.out.println(res);

        in.close();
    }

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

}

class Pos{
    int x;
    int y;

    public Pos(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }
}


            

活动打卡代码 AcWing 1240. 完全二叉树的权值

nighoc
2个月前

                import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    final int N = 100010;
    int[] w = new int[N];
    long[] sum = new long[N];

    public Main() throws IOException {
        int n = Integer.parseInt(in.readLine());
        int depth = (int) (Math.log(n) / Math.log(2)) + 1;

        String[] line = in.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            w[i] = Integer.parseInt(line[i]);
        }

        long max = Long.MIN_VALUE;
        int res = -1;
        for (int i = 1, j = 0; i <= depth; i++) {
            int k = (int)Math.pow(2, i - 1); // 深度为 i 的节点最多有 k 个
            while(j < n && k-- > 0) {
                sum[i] += w[j++];
            }

            if(sum[i] > max) {
                max = sum[i];
                res = i;
            }
        }
        System.out.println(res);    
        in.close();
    }

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

}


            

活动打卡代码 AcWing 282. 石子合并

nighoc
2个月前

                import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    final int N = 310, INF = Integer.MAX_VALUE;
    int[] s = new int[N];
    int[][] f = new int[N][N];
    int n;

    int dp(int l, int r) {
        if(f[l][r] != -1)
            return f[l][r];

        if(l == r)
            return 0;

        f[l][r] = INF;
        for (int i = l; i < r; i++) {
            f[l][r] = Math.min(f[l][r], dp(l, i) + dp(i + 1, r) + s[r] - s[l - 1]);
        }

        return f[l][r];
    }

    public Main() throws IOException {
        n = Integer.parseInt(in.readLine());
        String[] line = in.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            s[i] = Integer.parseInt(line[i - 1]);
            s[i] += s[i - 1]; // 前缀和
        }

        for (int i = 1; i <= n; i++) {
            Arrays.fill(f[i], 1, n + 1, -1);
        }

        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                f[i][j] = dp(i, j);
            }
        }


        System.out.println(f[1][n]);        
        in.close();
    }

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

}


            

题解 AcWing 282. 石子合并( java实现，循环实现和记忆化搜索)

nighoc
2个月前

                循环实现
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    final int N = 310, INF = Integer.MAX_VALUE;
    int[] s = new int[N];
    int[][] f = new int[N][N];
    int n;

    public Main() throws IOException {
        n = Integer.parseInt(in.readLine());
        String[] line = in.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            s[i] = Integer.parseInt(line[i - 1]);
            s[i] += s[i - 1]; // 前缀和
        }

        for (int len = 2; len <= n; len++) {
            for (int l = 1; l + len - 1 <= n; l++) {
                int r = l + len - 1;
                f[l][r] = INF;
                for (int k = l; k < r; k++) {
                    f[l][r] = Math.min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                }
            }
        }

        System.out.println(f[1][n]);

        in.close();
    }

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

}



记忆化搜索
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    final int N = 310, INF = Integer.MAX_VALUE;
    int[] s = new int[N];
    int[][] f = new int[N][N];
    int n;

    int dp(int l, int r) {
        if(f[l][r] != -1)
            return f[l][r];

        if(l == r)
            return 0;

        f[l][r] = INF;
        for (int i = l; i < r; i++) {
            f[l][r] = Math.min(f[l][r], dp(l, i) + dp(i + 1, r) + s[r] - s[l - 1]);
        }

        return f[l][r];
    }

    public Main() throws IOException {
        n = Integer.parseInt(in.readLine());
        String[] line = in.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            s[i] = Integer.parseInt(line[i - 1]);
            s[i] += s[i - 1]; // 前缀和
        }

        for (int i = 1; i <= n; i++) {
            Arrays.fill(f[i], 1, n + 1, -1);
        }

        System.out.println(dp(1, n));       
        in.close();
    }

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

}

            

0 评论

0 评论

0 评论

0 评论

1 评论

0 评论

0 评论

0 评论

0 评论

循环实现

记忆化搜索

0 评论