1.  最大K乘积问题

« 问题描述

 设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积。试设计一个算法，对于给定的I和k，求出I的最大k乘积。

例如十进制整数 1234 划分为 3 段可有如下情形：

1 × 2 × 34 = 68

1 × 23 × 4 = 92

12 × 3 × 4 = 144

« 编程任务

    对于给定的I 和k，编程计算I 的最大k 乘积。

« 数据输入

输入的第1 行中有2个正整数n和k。正整数n是序列的长度；正整数k是分割的段数。接下来的一行中是一个n位十进制整数。（n<=10）

  « 结果输出

          计算出的最大k乘积。

输入文件示例	输出文件示例
input.txt	output.txt
3 2 312	62

 

2. 游艇租用问题：

问题描述

长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1£i<j£n。试设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。

编程任务

对于给定的游艇出租站i到游艇出租站j之间的租金为r(i,j),1£i<j£n，编程计算从游艇出租站1到游艇出租站n所需的最少租金。

数据输入

由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n<=200），表示有n个游艇出租站。接下来的n-1行是r(i,j),1<=i<j<=n。

(例如：

3

5 15

7

表示一共有3个出租站点，其中

第1个站点到第2个的租金为5

第1个站点到第3个的租金为15

第2个站点到第3个的租金为7

)

结果输出

程序运行结束时，将计算出的从游艇出租站1到游艇出租站n所需的最少租金输出到文件output.txt中。

输入文件示例	输出文件示例
input.txt	output.txt
3 5 15	12
7
input.txt	output.txt
4	15
3 7 19
5 13
8

实现源码：

import java.io.*;
public class Main{
    public static void main(String[] args){
        K();
        least();
    }
    public static void K(){
        /*
        num[n]存放数字
        m[i][j]表示前i个元素分为j段
        m[i][j] = Max(m[k][j-1]*num[k:i])
        */ 
        try{
            //数据初始化
            BufferedReader fr=new BufferedReader(new FileReader("file//input_2.txt"));
            String[] firstLine = fr.readLine().split(" ");
            int n = Integer.parseInt(firstLine[0]);
            int k = Integer.parseInt(firstLine[1]);
            String[] secondLine=fr.readLine().split("");
            int[] num = new int[n+1];
            for(int i=1;i<=n;i++){
                num[i] = Integer.parseInt(secondLine[i-1]);
            }

            //结果数组m初始化
            int[][] m = new int[n+1][n+1];
            m[1][1] = num[1];
            for(int i=2;i<=n;i++){//初始情况，分为1段时
                m[i][1] = m[i-1][1]*10 + num[i];
            }

            //进行分段
            for(int part=2; part<=n; part++){//分为part段，最多即n段
                for(int len=part; len<=n; len++){//更新m[len][part]
                    int max = 0;
                    for(int median=1; median<len; median++){//寻找中间值median，寻找m[len][part]的最大值
                        int value = m[median][part-1]*sum(num,median+1,len);
                        max= max>value ? max : value;
                    }
                    m[len][part] = max;
                }
            }
            fr.close();
            
            //将结果写入文件
            FileWriter fw = new FileWriter(new File("file//output_2.txt"));
            fw.write(String.valueOf(m[n][k]));
            fw.close();
        }catch(Exception e){
            System.out.println(e);
        }
    }

    public static int sum(int[]num,int i,int j){//求数组num第i位到第j位的和
        int result=0;
        for(int k=i;k<=j;k++){
            result += num[k];
        }
        return result;
    }

    public static void least()
    {
        try{
            BufferedReader fr = new BufferedReader(new FileReader("file/input.txt"));
            int len = Integer.parseInt(fr.readLine());
            //出租点编号为0到len-1号

            //到各点的最小开销
            int[] cost = new int[len];
            for(int i=0;i<len;i++){
                cost[i] = i==0 ? 0 : 0Xffff;
            }

            //为距离数组赋值
            int[][] num = new int[len][len];
            for(int i=0;i<len-1;i++){
                String[] str = fr.readLine().split(" ");
                for(int j=0;j<str.length;j++){
                    num[i][i+1+j] = Integer.parseInt(str[j]);
                }
            }

            //len-1次循环，逐步向后更新到每个点的最小开销
            for(int i=0;i<len-1;i++){//根据第i个点到后面点的距离，更新最短距离
                for(int j=i+1;j<len;j++){
                    if( cost[j] > cost[i]+num[i][j] ){
                        cost[j] = cost[i]+num[i][j];
                    }
                }
            }
            fr.close();

            FileWriter fw = new FileWriter(new File("file//output.txt"));
            fw.write(String.valueOf(cost[len-1]));
            fw.close();
        }catch(Exception e){
            System.out.println(e);
        }
    }

}