个人空间 - AcWing

伟岸Lok

访客：982

发消息

离线：12小时前

活动打卡代码 AcWing 1018. 最低通行费

伟岸Lok
1天前

import java.io.*; import java.util.*; class Main{ static BufferedReader read = new BufferedReader(new InputStreamReader(System.in)); static int[][] a = new int[110][110]; static int[][][] dp = new int[110][110][220]; static int INF = 0x3f3f3f3f; public static void main(String[] args) throws Exception{ int n = Integer.valueOf(read.readLine()); for(int i = 1; i <= n; i++){ String[] ss = read.readLine().split(" +"); for(int j = 1; j <= n; j++){ a[i][j] = Integer.valueOf(ss[j - 1]); } } for(int i = 0; i <= n; i++){ for(int j = 0; j <= n; j++){ Arrays.fill(dp[i][j], INF); } } dp[1][1][0] = a[1][1]; for(int k = 1; k <= 2 * n - 1; k++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(i - 1 >= 1) dp[i][j][k] = Math.min(dp[i - 1][j][k - 1] + a[i][j], dp[i][j][k]); if(j + 1 <= n) dp[i][j][k] = Math.min(dp[i][j + 1][k - 1] + a[i][j], dp[i][j][k]); if(i + 1 <= n) dp[i][j][k] = Math.min(dp[i + 1][j][k - 1] + a[i][j], dp[i][j][k]); if(j - 1 >= 1) dp[i][j][k] = Math.min(dp[i][j - 1][k - 1] + a[i][j], dp[i][j][k]); } } } int min = INF; for(int i = 0; i <= 2 * n - 1; i++){ min = Math.min(min, dp[n][n][i]); } System.out.println(min); } }

活动打卡代码 AcWing 1015. 摘花生

伟岸Lok
1天前

dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + a[i][j];

import java.io.*;
class Main{
    static int[][] dp = new int[110][110],a = new int[110][110];
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception{
        int t = Integer.valueOf(read.readLine());
        while(t-- > 0){
            String[] ss = read.readLine().split(" ");
            int r = Integer.valueOf(ss[0]);
            int c = Integer.valueOf(ss[1]);
            for(int i = 1; i <= r; i++){
                ss = read.readLine().split(" ");
                for(int j = 1; j <= c; j++){
                    a[i][j] = Integer.valueOf(ss[j - 1]);
                }
            }        
            for(int i = 1; i <= r; i++){
                for(int j = 1; j <= c; j++){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
                }
            }
            System.out.println(dp[r][c]);
        }
    }
}

活动打卡代码 AcWing 338. 计数问题

伟岸Lok
3天前

                import java.io.*;
import java.util.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static int count(int n, int x){
        String s = String.valueOf(n);
        int cnt = 0, len = s.length();
        for(int i = 0; i < len; i++){
            int left = i > 0 ? Integer.valueOf(s.substring(0, i)) : 0;
            if(x != 0) cnt += left * Math.pow(10, len - (i + 1));
            //如果是0，特殊处理下
            else cnt += (left - 1) * Math.pow(10, len - (i + 1));
            int right = i < len - 1 ? Integer.valueOf(s.substring(i + 1, len)) : 0;
            int cur = s.charAt(i) - '0';
            if(cur == x){
                cnt += right + 1;
            }else if(cur > x){
                cnt += Math.pow(10, len - (i + 1));
            }
        }
        return cnt;
    }

    public static void main(String[] args) throws Exception{
        while(true){
            String[] ss = read.readLine().split(" ");
            int left = Integer.valueOf(ss[0]);
            int right = Integer.valueOf(ss[1]);
            if(left > right){
                int tmp = left;
                left = right; 
                right = tmp;
            }
            if(left == 0 && right == 0) break;
            for(int i = 0; i < 10; i++){
                int c1 = count(left - 1, i);
                int c2 = count(right, i);
                System.out.print((c2 - c1) + " ");
            }
            System.out.println();
        }
    }
}

            

活动打卡代码 AcWing 901. 滑雪

伟岸Lok
5天前

import java.io.*;
import java.util.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 310, n, m;
    static int[][] a = new int[N][N];
    static int[][] dp = new int[N][N];
    static int[][] dir = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    public static void main(String[] args) throws Exception{
        String[] ss = read.readLine().split(" ");
        n = Integer.valueOf(ss[0]);
        m = Integer.valueOf(ss[1]);
        for(int i = 0; i < n; i++){
            ss = read.readLine().split(" ");
            for(int j = 0; j < m; j++){
                a[i][j]  = Integer.valueOf(ss[j]);
            }
        }
        int max = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                max = Math.max(max, dfs(i, j));
            }
        }
        System.out.println(max);
    }

    public static int dfs(int i, int j){
        if(dp[i][j] != 0) return dp[i][j];
        dp[i][j] = 1;
        for(int k = 0; k < 4; k++){
            int x = i + dir[k][0];
            int y = j + dir[k][1];
            if(x >= 0 && x < n && y >= 0 && y < m && a[x][y] < a[i][j]){
                dp[i][j] = Math.max(dp[i][j], dfs(x, y) + 1);
            }
        }
        return dp[i][j];
    }


}

下面是个人没看视频手撸代码

import java.io.*;
import java.util.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 310, n, m;
    static int[][] a = new int[N][N];
    static Map<Integer, Integer> map = new HashMap();
    static int[][] dir = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    public static void main(String[] args) throws Exception{
        String[] ss = read.readLine().split(" ");
        n = Integer.valueOf(ss[0]);
        m = Integer.valueOf(ss[1]);
        for(int i = 0; i < n; i++){
            ss = read.readLine().split(" ");
            for(int j = 0; j < m; j++){
                a[i][j]  = Integer.valueOf(ss[j]);
            }
        }
        int max = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                max = Math.max(max, dfs(i, j, a));
            }
        }
        System.out.println(max);
    }

    public static int dfs(int i, int j, int[][] a){
        int ref = reflect(i, j, a[0].length);
        if(map.containsKey(ref)) return map.get(ref);
        int ans = 1;
        for(int k = 0; k < 4; k++){
            int x = i + dir[k][0];
            int y = j + dir[k][1];
            if(x >= 0 && x < n && y >= 0 && y < m && a[x][y] < a[i][j]){
                ans = Math.max(ans, dfs(x, y, a) + 1);
            }
        }
        map.put(ref, ans);
        return ans;
    }


    public static int reflect(int i, int j, int col){
        return i * col + j;
    }
}

活动打卡代码 AcWing 91. 最短Hamilton路径

伟岸Lok
5天前

                import java.io.*;
import java.util.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 20, M = 1 << N;
    static int[][] dp = new int[M][N];
    static int[][]  w = new int[N][N];
    public static void main(String[] args) throws Exception{
        int n = Integer.valueOf(read.readLine());
        for(int i = 0; i < n; i++){
            String[] ss = read.readLine().split(" ");
            for(int j = 0; j < n; j++){
                w[i][j] = Integer.valueOf(ss[j]);
            }
        }
        for(int i = 0; i < M; i++)  Arrays.fill(dp[i], 0x3f3f3f3f);
        dp[1][0] = 0;
        for(int i = 1; i < 1 << n; i++){
            for(int j = 0; j < n; j++){
                //j 为最后到达城市，所以状态i右移j位必须为1
                if((i >> j & 1) != 0){
                    for(int k = 0; k < n; k++){
                        //dp[i][j] = dp[k_s][k] + w[k][j]
                        int k_s = i - (1 << j);
                        //k_s 为 i减去状态j， 左边最后抵达k， 所以k位必须为1
                        if((k_s >> k & 1) != 0){
                            dp[i][j] = Math.min(dp[i][j], dp[k_s][k] + w[k][j]);
                        }
                    }
                }
            }
        }
        System.out.println(dp[(1 << n) - 1][n - 1]);
    }
}

            

活动打卡代码 AcWing 285. 没有上司的舞会

伟岸Lok
5天前

                import java.io.*;
import java.util.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 6010, idx = 0;
    static int[] e = new int[N], ne = new int[N], adj = new int[N];
    static Map<Integer, Integer> happy;
    static int[][] dp = new int[N][2];
    public static void main(String[] args) throws Exception{
        int n = Integer.valueOf(read.readLine());
        int[] in = new int[n + 1];
        Arrays.fill(adj, -1);
        happy = new HashMap();
        for(int i = 1; i <= n; i++){
            happy.put(i, Integer.valueOf(read.readLine()));
        }
        for(int i = 1; i < n; i++){
            String[] ss = read.readLine().split(" ");
            int a = Integer.valueOf(ss[0]);
            int b = Integer.valueOf(ss[1]);
            add(b, a);
            in[a] ++;
        }
        int root = 0;
        for(int i = 1; i <= n; i++) if(in[i] == 0)  root = i;
        dfs(root);
        System.out.println(Math.max(dp[root][0], dp[root][1]));
    }

    public static void dfs(int node){
        dp[node][1] = happy.get(node);
        for(int i = adj[node]; i != -1; i = ne[i]){
            int j = e[i];
            dfs(j);
            dp[node][0] += Math.max(dp[j][0], dp[j][1]);
            dp[node][1] += dp[j][0];
        }

    }
    public static void add(int a, int b){
        e[idx] = b; ne[idx] = adj[a]; adj[a] = idx++;
    }
}

            

活动打卡代码 AcWing 291. 蒙德里安的梦想

伟岸Lok
6天前

                import java.io.*;
import java.util.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 12, M = 1 << N;
    public static void main(String[] args) throws Exception{
        long[][] dp = new long[N][M];
        String[] ss;
        while(true){
            ss = read.readLine().split(" ");
            int n = Integer.valueOf(ss[0]);
            int m = Integer.valueOf(ss[1]);
            if(n == 0 && m == 0) break;

            //初始化dp
            for(int i = 0; i < N; i++)  Arrays.fill(dp[i], 0L);
            dp[0][0] = 1;

            for(int i = 1; i <= m; i++){
                for(int j = 0; j < 1 << n; j++){
                    for(int k = 0; k < 1 << n; k++){

                        if((j & k) == 0 && valid(j | k, n)){
                            dp[i][j] += dp[i - 1][k];
                        }
                    }
                }
            }
            System.out.println(dp[m][0]);
        }
    }
    //判断二进制相邻的0的个数是否偶数，如果偶数返回true
    public static boolean valid(int a, int n){
        int cnt = 0;
        for(int j = 0; j < n; j++){
            if((a >> j & 1) != 0){
                if((cnt & 1) != 0)    return false;
                cnt = 0;
            }else{
                cnt++;
            }
        }
        //判断最后的0是否为偶数
        if((cnt & 1) != 0)    return false;
        return true;
    }
}

            

题解 AcWing 291. 简单易懂，慢点的未优化的代码， JAVA

伟岸Lok
6天前

                import java.io.*;
import java.util.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 12, M = 1 << N;
    public static void main(String[] args) throws Exception{
        long[][] dp = new long[N][M];
        String[] ss;
        while(true){
            ss = read.readLine().split(" ");
            int n = Integer.valueOf(ss[0]);
            int m = Integer.valueOf(ss[1]);
            if(n == 0 && m == 0) break;

            //初始化dp
            for(int i = 0; i < N; i++)  Arrays.fill(dp[i], 0L);
            dp[0][0] = 1;

            for(int i = 1; i <= m; i++){
                for(int j = 0; j < 1 << n; j++){
                    for(int k = 0; k < 1 << n; k++){

                        if((j & k) == 0 && valid(j | k, n)){
                            dp[i][j] += dp[i - 1][k];
                        }
                    }
                }
            }
            System.out.println(dp[m][0]);
        }
    }
    //判断二进制相邻的0的个数是否偶数，如果偶数返回true
    public static boolean valid(int a, int n){
        int cnt = 0;
        for(int j = 0; j < n; j++){
            if((a >> j & 1) != 0){
                if((cnt & 1) != 0)    return false;
                cnt = 0;
            }else{
                cnt++;
            }
        }
        //判断最后的0是否为偶数
        if((cnt & 1) != 0)    return false;
        return true;
    }
}

            

活动打卡代码 AcWing 900. 整数划分

伟岸Lok
9天前

完全背包问题解法：

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] v = new int[n + 1];
        int mod = (int) 1e9 + 7;
        for(int i = 1; i <= n; i++) v[i] = i;
        int[][] dp = new int[n + 1][n + 1];
        for(int i = 1; i <= n; i++) dp[i][0] = 1;  //从前i个数字选，体积恰好是0的选法， 都是1种，就是全部都不选。
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = dp[i - 1][j];
                if(j - v[i] >= 0)   dp[i][j] = (dp[i][j] + dp[i][j - v[i]]) % mod;
            }
        }
        System.out.println(dp[n][n]);
    }
}

完全背包问题空间优化解法

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] v = new int[n + 1];
        int mod = (int) 1e9 + 7;
        for(int i = 1; i <= n; i++) v[i] = i;
        int[] dp = new int[n + 1];
        dp[0] = 1;  //从前i个数字选，体积恰好是0的选法， 都是1种，就是全部都不选。
        for(int i = 1; i <= n; i++){
            for(int j = v[i]; j <= n; j++){
                dp[j] = (dp[j] + dp[j - v[i]]) % mod;
            }
        }
        System.out.println(dp[n]);
    }
}

按和为i，个数为j进行划分

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] v = new int[n + 1];
        int mod = (int) 1e9 + 7;
        int[][] dp = new int[n + 1][n + 1];
        for(int i = 1; i <= n; i++) dp[i][1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = dp[i - 1][j - 1];
                if(i >= j) dp[i][j] = (dp[i][j] + dp[i - j][j]) % mod;
            }
        }

        int ans = 0;
        for(int i = 1; i <= n; i++){
            ans = (ans + dp[n][i]) % mod;
        }
        System.out.println(ans);
    }
}

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

伟岸Lok
13天前

                import java.io.*;
import java.util.*;

class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception{
        int n = Integer.valueOf(read.readLine());
        String[] ss = read.readLine().split(" ");
        int[] a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = Integer.valueOf(ss[i]);
        }
        int[] sum = new int[n + 1];
        int[][] dp = new int[n + 1][n + 1];

        for(int i = 1; i <= n; i++){
            sum[i] = sum[i - 1] + a[i - 1];
        }

        for(int len = 2; len <= n; len++){
            for(int l = 1; l + len - 1 <= n; l++){
                int r = l + len - 1;
                dp[l][r] = 0x3f3f3f3f;   //初始化
                for(int k = l; k < r; k++){
                    dp[l][r] = Math.min(dp[l][r], 
                    dp[l][k] + dp[k + 1][r] + sum[r] - sum[l - 1]);

                }
            }
        }
        System.out.println(dp[1][n]);
    }
}

            

评论列表：

评论列表：

评论列表：

评论列表：

评论列表：

评论列表：

评论列表：

评论列表：

评论列表：

评论列表：