java算法巩固训练day02

乘积最大

  • 给出一个n位数，在数字中间添加k个乘号,使得最终的乘积最大。
  • 非记忆化版本！！！
package Test.ACM;

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

/*

4  2
1231

4 1
6666

*/

public class Main {
    public static void main(String[] args) {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        while(in.hasNext()) {
            int n = in.nextInt();
            int m = in.nextInt();
            String tmp = in.next();
            char[] str = tmp.toCharArray();
            BigInteger[][] dp = new BigInteger[n + 1][m + 1];
            BigInteger[][] sum = new BigInteger[n + 1][n + 1];
            BigInteger now;
            BigInteger zero = BigInteger.ZERO;
            BigInteger ten = BigInteger.TEN;
            for(int i = 0; i <= n; ++i) { // 注意要初始化，否则创建的BigInteger类对象为null，计算过程中会出现错误
                for(int j = 0; j <= n; ++j) {
                    sum[i][j] = zero;
                }
                for(int j = 0; j <= m; ++j) {
                    dp[i][j] = zero;
                }
            }
            for(int i = 1; i <= n; ++i) {
                sum[i][i] = new BigInteger(String.valueOf(str[i - 1]));
                for(int j = i + 1; j <= n; ++j) {
                    now = new BigInteger(String.valueOf(str[j - 1]));
                    sum[i][j] = sum[i][j - 1].multiply(ten).add(now);
                }
            }
            for(int i = 1; i <= n; ++i) { // 前i位插入0个乘号即为前i位数字组成的数
                dp[i][0] = sum[1][i];
            }
            for(int i = 1; i <= n; ++i) { // 枚举第i位
                for(int j = 1; j <= Math.min(i - 1, m); ++j) { // 枚举使用第j个括号，最大不超过i-1或者k，也就是在第i位后面放一个乘号
                    for(int k = j; k < i; ++k) { // 枚举在位置[k, i)
                        now = dp[k][j - 1].multiply(sum[k + 1][i]);
                        int dif = dp[i][j].compareTo(now);
                        if(dif < 0) {
                            dp[i][j] = now;
                        }
                    }
                }
            }
            System.out.println(dp[n][m]);
        }
        out.close();
    }
}
class InputReader {
    BufferedReader buf;
    StringTokenizer tok;
    InputReader() {
        buf = new BufferedReader(new InputStreamReader(System.in));
    }
    boolean hasNext() {
        while(tok == null || !tok.hasMoreElements()) {
            try {
                tok = new StringTokenizer(buf.readLine());
            }
            catch(Exception e) {
                return false;
            }
        }
        return true;
    }
    String next() {
        if(hasNext()) return tok.nextToken();
        return null;
    }
    int nextInt() {
        return Integer.parseInt(next());
    }
    long nextLong() {
        return Long.parseLong(next());
    }
    double nextDouble() {
        return Double.parseDouble(next());
    }
    BigInteger nextBigInteger() {
        return new BigInteger(next());
    }
    BigDecimal nextBigDecimal() {
        return new BigDecimal(next());
    }
}
  • 记忆化搜索版本：定义dp[i][j] 表示前i位使用j个乘号相乘得到的最大值。dfs一般是放一个乘号就减一个，递归边界是k==0，同时记忆化子答案，这样按着递推的公式就能轻松写出代码！
package Test.ACM;

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

/*

4  2
1231

4 1
6666

*/

public class Main {
    static BigInteger[][] dp = new BigInteger[45][10];
    static BigInteger[][] sum = new BigInteger[45][45];
    static int n;
    static BigInteger negOne = new BigInteger("-1");
    public static void main(String[] args) {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        while(in.hasNext()) {
            n = in.nextInt();
            int m = in.nextInt();
            String tmp = in.next();
            char[] str = tmp.toCharArray();
            BigInteger now;
            BigInteger zero = BigInteger.ZERO; // 0
            BigInteger ten = BigInteger.TEN; // 10
            for(int i = 0; i <= n; ++i) { // 注意要初始化，否则创建的BigInteger类对象为null，计算过程中会出现错误
                for(int j = 0; j <= n; ++j) {
                    sum[i][j] = zero;
                }
                for(int j = 0; j <= m; ++j) {
                    dp[i][j] = negOne; // 初始化为-1，做记忆化搜索
                }
            }
            for(int i = 1; i <= n; ++i) {
                sum[i][i] = new BigInteger(String.valueOf(str[i - 1]));
                for(int j = i + 1; j <= n; ++j) {
                    now = new BigInteger(String.valueOf(str[j - 1]));
                    sum[i][j] = sum[i][j - 1].multiply(ten).add(now);
                }
            }
            System.out.println(dfs(n, m));
        }
        out.close();
    }
    public static BigInteger dfs(int d, int k) {
        if(k == 0) return dp[d][k] = sum[1][d]; // 边界条件：剩下0个括号
        if(dp[d][k].compareTo(negOne) > 0) return dp[d][k]; // 记忆化搜索
        BigInteger now;
        int dif;
        for(int j = k; j < d; ++j) { // 在区间[k, d) 每个位置放一个括号
            now = dfs(j, k - 1).multiply(sum[j + 1][d]);  
            dif = dp[d][k].compareTo(now);
            if(dif < 0) dp[d][k] = now;
        }
        return dp[d][k]; // 返回结果
    }
}
class InputReader {
    BufferedReader buf;
    StringTokenizer tok;
    InputReader() {
        buf = new BufferedReader(new InputStreamReader(System.in));
    }
    boolean hasNext() {
        while(tok == null || !tok.hasMoreElements()) {
            try {
                tok = new StringTokenizer(buf.readLine());
            }
            catch(Exception e) {
                return false;
            }
        }
        return true;
    }
    String next() {
        if(hasNext()) return tok.nextToken();
        return null;
    }
    int nextInt() {
        return Integer.parseInt(next());
    }
    long nextLong() {
        return Long.parseLong(next());
    }
    double nextDouble() {
        return Double.parseDouble(next());
    }
    BigInteger nextBigInteger() {
        return new BigInteger(next());
    }
    BigDecimal nextBigDecimal() {
        return new BigDecimal(next());
    }
}

动态规划DP

  • POJ 3176 Cow Bowling
  • 记忆化搜索
package Test.ACM;

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

/*

定义：dp[i][j]表示前i行第j列已走路径和的最大值
显然，对于第i层的第j个位置，往下看，只有2个选择，那么递推公式为
dp[i][j] = a[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1])
非递归从后往前遍历，相当于深搜的回溯
递归要从前往后看，递归到底层，回溯从后往前统计，注意使用记忆化搜索，不然会造成重复计算大量相同子问题

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

*/

public class Main {
    static int n;
    static int[][] mp = new int[400][400];
    static int[][] dp = new int[400][400];
    public static void main(String[] args) {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        while(in.hasNext()) {
            n = in.nextInt();
            for(int i = 0; i <= n; ++i) {
                for(int j = 0; j <= n; ++j) {
                    mp[i][j] = 0; // 初始化为0
                    dp[i][j] = -1; // 初始化为-1，用于记忆化搜索
                }
            }
            for(int i = 1; i <= n; ++i) {
                for(int j = 1; j <= i; ++j) {
                    mp[i][j] = in.nextInt();
                }
            }
            System.out.println(dfs(1, 1)); // 站在最高点往下搜索
        }
        out.close();
    }
    public static boolean check(int x, int y) {
        if(x < 1 || y < 1 || x > n || y > n) return false;
        return true;
    }
    public static int dfs(int x, int y) {
        if(!check(x, y)) return 0;
        else if(dp[x][y] != -1) return dp[x][y];
        else return dp[x][y] = mp[x][y] + Math.max(dfs(x + 1, y), dfs(x + 1, y + 1));
    }
}
class InputReader {
    BufferedReader buf;
    StringTokenizer tok;
    InputReader() {
        buf = new BufferedReader(new InputStreamReader(System.in));
    }
    boolean hasNext() {
        while(tok == null || !tok.hasMoreElements()) {
            try {
                tok = new StringTokenizer(buf.readLine());
            }
            catch(Exception e) {
                return false;
            }
        }
        return true;
    }
    String next() {
        if(hasNext()) return tok.nextToken();
        return null;
    }
    int nextInt() {
        return Integer.parseInt(next());
    }
    long nextLong() {
        return Long.parseLong(next());
    }
    double nextDouble() {
        return Double.parseDouble(next());
    }
    BigInteger nextBigInteger() {
        return new BigInteger(next());
    }
    BigDecimal nextBigDecimal() {
        return new BigDecimal(next());
    }
}
  • 非递归版本
package Test.ACM;

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

/*

定义：dp[i][j]表示前i行第j列已走路径和的最大值
显然，对于第i层的第j个位置，往下看，只有2个选择，那么递推公式为
dp[i][j] = a[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1])
非递归从后往前遍历，相当于深搜的回溯
递归要从前往后看，递归到底层，回溯从后往前统计，注意使用记忆化搜索

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

*/

public class Main {
    static int n;
    static int[][] mp = new int[400][400];
    static int[][] dp = new int[400][400];
    public static void main(String[] args) {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        while(in.hasNext()) {
            n = in.nextInt();
            for(int i = 0; i <= n; ++i) {
                for(int j = 0; j <= n; ++j) {
                    dp[i][j] = mp[i][j] = 0;
                }
            }
            for(int i = 1; i <= n; ++i) {
                for(int j = 1; j <= i; ++j) {
                    mp[i][j] = in.nextInt();
                }
            }
            for(int i = n; i > 0; --i) {
                for(int j = 1; j <= i; ++j) {
                    dp[i][j] = mp[i][j] + Math.max(dp[i + 1][j], dp[i + 1][j + 1]);
                }
            }
            System.out.println(dp[1][1]);
        }
        out.close();
    }
}
class InputReader {
    BufferedReader buf;
    StringTokenizer tok;
    InputReader() {
        buf = new BufferedReader(new InputStreamReader(System.in));
    }
    boolean hasNext() {
        while(tok == null || !tok.hasMoreElements()) {
            try {
                tok = new StringTokenizer(buf.readLine());
            }
            catch(Exception e) {
                return false;
            }
        }
        return true;
    }
    String next() {
        if(hasNext()) return tok.nextToken();
        return null;
    }
    int nextInt() {
        return Integer.parseInt(next());
    }
    long nextLong() {
        return Long.parseLong(next());
    }
    double nextDouble() {
        return Double.parseDouble(next());
    }
    BigInteger nextBigInteger() {
        return new BigInteger(next());
    }
    BigDecimal nextBigDecimal() {
        return new BigDecimal(next());
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,319评论 5赞 459
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,801评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,567评论 0赞 319
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,156评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,019评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,090评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,500评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,192评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,474评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,566评论 2赞 309
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,338评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,212评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,572评论 3赞 298
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,890评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,169评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,478评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,661评论 2赞 335