第九周习题

ゝ一世哀愁。 2022-10-21 03:59 177阅读 0赞

### 记录 ###

*  A、最大字段和升级版
 *   *  代码
 *  B、斜线最大最小值
 *   *  代码
 *  C、矩阵连乘问题-备忘录法求最优值
 *   *  代码
 *  D、矩阵连乘问题-动态规划求最优值
 *   *  代码
 *  E、矩阵连乘问题-构造最优解
 *   *  代码
 *  F、石子合并问题
 *   *  代码

# A、最大字段和升级版 #

**题目描述**

*  使用动态规划算法求整数数组（可能包含负整数）的最大子段和，以及和最大子段的起始位置和结束位置：  
    例如：输入数组(6,-1,5,4,-7)，输出14, 1,4，其中14表示最大子段和，1表示和最大的子段从第1个数字开始，4表示和最大的子段到第4个数字结束，即(6, -1 , 5, 4)。

**输入**

*  每组输入两行，第1行为数组中包含的整数个数n，第2行为n个整数（可能包含负整数），两两之间用空格隔开。

**输出**

*  输出最大子段和，以及和最大子段的起始位置和结束位置，两两之间用空格隔开。

**样例输入 Copy**

5
    6 -1 5 4 -7

**样例输出 Copy**

14 1 4

> 【这个题目，直接贯穿了我的整个五一假期，还多加了几天的时间，其实大部分代码我都写好了，只有一个地方有问题，就是输入1，它只会输出1 0 0，不是输出1 1 1 ，然而就是这个问题困扰了我好久好久，然后就是，因为五一也出去完了，更加没思路了，好不容易问了室友才恍然大悟，就是我设置的起始位置和终止位置的初始化一直都是设置的0，改成1就行了，所以我那么久CSDN也没找到答案，哭了~我室友是直接在循环的过程记录起始位置的，所以直接调用输出就行，但是我懒得改了，放一个链接吧，对后面的题目有很大帮助哈：[和我一样的题目~戳她戳她！][Link 1]】

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
        
    	public static int []a = new int[105];
    	public static int []b = new int[105];
    	public static int n,maxSum,index,maxIndex,max_S;
    	
    	public static void solve(){ 
    		b[0] = a[0];
    		maxSum = b[0];
    		index = 1;
    		maxIndex = 1;
    		   
    		for(int j=1;j<n;j++){ 
    			   
    			if(b[j-1]>0)
    				b[j] = b[j-1]+a[j];
    			else{ 
    				b[j] = a[j];
    				
    			}
    			   
    			if(b[j]>maxSum){ 
    				maxSum = b[j];
    				maxIndex = j+1;
    			}
    			
    		   max_S = maxSum;
     		   for(int i = maxIndex-1;i>=0;i--){ 
     			   max_S-=a[i];
     			   if(max_S==0)
     				   index = i+1;
     		   }
    	}
    }
    	
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    	   Scanner sc = new Scanner(System.in);
           while(sc.hasNext()){ 
        	   n = sc.nextInt();
        		   for(int i=0;i<n;i++)
            		   a[i] = sc.nextInt();
            	   solve();
            	   System.out.println(maxSum+" "+index+" "+maxIndex);
        	   }
        	   
       		   
           }
       }

# B、斜线最大最小值 #

**题目描述**

*  求如图所示一个上三角矩阵中每一条斜线中的最大元素(L)和最小元素(S)。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODIzMTE4_size_16_color_FFFFFF_t_70]  
    **输入**
 *  每组输入包括两部分，一部分为数字n，表示三角矩阵的行数。
 *  第二部分即为三角矩阵。

**输出**

*  每一个对角线输出一行，每行包括Lx=Max,  
    Sx=Min，其中x为斜线序号（序号从1开始），Max为该斜线上的最大值，Min为该斜线上的最小值。

**样例输入 Copy**

6
    1 3 5 7 11 20
    0 6 8 2 3 13
    0 0 7 4 8 9
    0 0 0 18 3 10
    0 0 0 0 12 6
    0 0 0 0 0 15

**样例输出 Copy**

L1=18, S1=1
    L2=8, S2=3
    L3=10, S3=2
    L4=9, S4=3
    L5=13, S5=11
    L6=20, S6=20

【有问题的话就戳上面的那个链接吧~我就是根据那个来的】

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	public static int a[][] = new int[105][105];
    	public static int max,min;
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int n = sc.nextInt();
    			
    			max = 0;min = 0;
    			for(int i=1;i<=n;i++)
    				for(int j=1;j<=n;j++)
    					a[i][j] = sc.nextInt();
    			
    			
    			for(int r=1;r<=n;r++){ 
    				max = a[1][r];
    				min = a[1][r];
    				
    				for(int i=1;i<=n-r+1;i++){ 
    					int j=r+i-1;
    					
    					if(max<a[i][j])//最大值
    						max = a[i][j];
    					
    					else if(min>a[i][j])//最小值
    						min = a[i][j];
    				}
    				
    				System.out.println("L"+r+"="+max+", "+"S"+r+"="+min);
    				
    			}
    				
    		}
    
    	}
    
    }

# C、矩阵连乘问题-备忘录法求最优值 #

**题目描述**

*  使用备忘录法求解矩阵连乘问题，输出最少乘法次数。

**输入**

*  每组数据包括两行，第一行为数组长度n，第二行为存储矩阵维数的一维数组。

**输出**

*  矩阵连乘最优计算次数。

**样例输入 Copy**

7
    30 35 15 5 10 20 25

**样例输出 Copy**

15125

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	public static int m[][] = new int[105][105];
    	public static int s[][] = new int[105][105];
    	public static int p[] = new int[105];
    	public static int n;
    	
    	public static int lookup(int i,int j){ 
    		
    		for(int k=0;k<n;k++)
    			for(int t=0;t<n;t++)
    				m[k][t] = 0;
    		
    		
    		if(m[i][j]>0)
    			return m[i][j];
    		
    		if(i==j)
    			return 0;
    		int u = lookup(i+1,j)+p[i-1]*p[i]*p[j];
    		s[i][j] = i;
    		for(int k = i+1;k<j;k++){ 
    			int t = lookup(i,k)+lookup(k+1,j)+p[i-1]*p[k]*p[j];
    			if(t<u){ 
    				u = t;
    				s[i][j] = k;
    			}
    			
    		}
    		m[i][j] = u;
    		return u;
    	}
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			n = sc.nextInt();
    			for(int i=0;i<n;i++)
    				p[i] = sc.nextInt();
    			System.out.println(lookup(1,n-1));
    		}
    
    	}
    
    }

# D、矩阵连乘问题-动态规划求最优值 #

**题目描述**

*  使用动态规划算法求解矩阵连乘问题，输出最少乘法次数。

**输入**

*  每组数据包括两行，第一行为数组长度n，第二行为存储矩阵维数的一维数组。

**输出**

*  矩阵连乘最优计算次数。

**样例输入 Copy**

7
    30 35 15 5 10 20 25

**样例输出 Copy**

15125

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	
    	public static int m[][] = new int[105][105];
    	public static int s[][] = new int[105][105];
    	public static int p[] = new int[105];
    	public static int n;
    
    	public static void matrixChain(int []p,int [][]m,int [][]s){ 
    		
    		for(int i=1;i<=n;i++)
    			m[i][i] = 0;
    		
    		for(int r=2;r<=n;r++)
    			for(int i=1;i<=n-r+1;i++){ 
    				
    				int j = i+r-1;
    				m[i][j] = m[i+1][j]+p[i-1]*p[i]*p[j];
    				s[i][j] = i;
    				
    				for(int k = i+1;k<j;k++){ 
    					
    					int t = m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
    					if(t<m[i][j]){ 
    						m[i][j] = t;
    						s[i][j] = k;
    					}
    				}
    			}
    	}
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			n = sc.nextInt();
    			for(int i=0;i<n;i++)
    				p[i] = sc.nextInt();
    			matrixChain(p,m,s);
    			System.out.println(m[1][n-1]);
    		}
    
    	}
    
    }

# E、矩阵连乘问题-构造最优解 #

**题目描述**

*  使用动态规划算法求解矩阵连乘问题。

**输入**

*  每组数据包括两行，第一行为数组长度n，第二行为存储矩阵维数的一维数组。

**输出**

*  矩阵连乘最优计算次序。

**样例输入 Copy**

7
    30 35 15 5 10 20 25

**样例输出 Copy**

A[2:2] * A[3:3]
    A[1:1] * A[2:3]
    A[4:4] * A[5:5]
    A[4:5] * A[6:6]
    A[1:3] * A[4:6]

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	
    	public static int m[][] = new int[105][105];
    	public static int s[][] = new int[105][105];
    	public static int p[] = new int[105];
    	public static int n;
    
    	public static void matrixChain(int []p,int [][]m,int [][]s){ 
    		
    		for(int i=1;i<=n;i++)
    			m[i][i] = 0;
    		
    		for(int r=2;r<=n;r++)
    			for(int i=1;i<=n-r+1;i++){ 
    				
    				int j = i+r-1;
    				m[i][j] = m[i+1][j]+p[i-1]*p[i]*p[j];
    				s[i][j] = i;
    				
    				for(int k = i+1;k<j;k++){ 
    					
    					int t = m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
    					if(t<m[i][j]){ 
    						m[i][j] = t;
    						s[i][j] = k;
    					}
    				}
    			}
    	}
    	
    	public static void traceback(int [][]s,int i,int j){ 
    		if(i==j)
    			return;
    		traceback(s,i,s[i][j]);
    		int t = s[i][j]+1;
    		traceback(s,t,j);
    		System.out.println("A["+i+":"+s[i][j]+"] * "+"A["+t+":"+j+"]");
    	}
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			n = sc.nextInt();
    			for(int i=0;i<n;i++)
    				p[i] = sc.nextInt();
    			matrixChain(p,m,s);
    			traceback(s,1,n-1);
    			
    		}
    
    	}
    
    }

# F、石子合并问题 #

**题目描述**

*  在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。例如：输入\{1，2，3，4，5\}，输出33。【3+6+9+15=33】

**输入**

*  本题应该处理到文件尾，每组输入包括两行，第一行为石子堆的个数n，第二行则为每堆石子的个数。

**输出**

*  输出最小花费。

**样例输入 Copy**

5
    1 2 3 4 5

**样例输出 Copy**

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	
    	public static int m[][] = new int[105][105];
    	public static int s[][] = new int[105][105];
    	public static int p[] = new int[105];
    	public static int n;
    
    	public static void matrixChain(int []p,int [][]m,int [][]s){ 
    		
    		for(int i=1;i<=n;i++)
    			m[i][i] = 0;
    		
    		for(int r=2;r<=n;r++)
    			for(int i=1;i<=n-r+1;i++){ 
    				
    				int j = i+r-1;
    				m[i][j] = m[i+1][j]+s[i][j];
    				
    				for(int k = i+1;k<j;k++){ 
    					
    					int t = m[i][k]+m[k+1][j]+s[i][j];
    					if(t<m[i][j]){ 
    						m[i][j] = t;
    					}
    				}
    			}
    	}
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			n = sc.nextInt();
    			for(int i=1;i<=n;i++)
    				p[i] = sc.nextInt();
    			
    			for(int i=1;i<=n;i++)
    				s[i][i] = p[i];
    			
    			for(int i=1;i<=n;i++)
    				for(int j=i+1;j<=n;j++)
    					s[i][j] = s[i][j-1]+p[j];
    			matrixChain(p,m,s);
    			System.out.println(m[1][n]);
    		}
    
    	}
    
    }

> 【鉴于小编五一的时候学骑自行车摔伤了，所以就不和你们唠嗑了，小编虽然五一摔伤了，但是还是和室友出去玩了，去拍了很多照片，吃了臭豆腐，吃了炸鸡，吃了凉皮，吃了好多好多东西，O(∩\_∩)O哈哈~，开心！】
> 
> > 句子君：  
> > “但是啊，这世界上不是所有的事情都能如你所愿，有样东西必定会成为你成功的绊脚石，知道是什么吗？就是人的感情！无聊的嫉妒、傲慢、偏见、迷恋都是绊脚石，压制住这些感情，权衡眼前的利益取舍，这就是胜负的关键，只有成功才能开创人生道路，不管别人怎样把你当傻瓜，怎样被社会无视，只要拿出成果就会让人重新认识你，只要通过这一场考试，就能使生活环境发生巨变，被一时感情冲昏而损失利益的只能称之为傻瓜。”

[Link 1]: https://blog.csdn.net/qq_46555032/article/details/116278412
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODIzMTE4_size_16_color_FFFFFF_t_70]: /images/20221021/826a9f83d6234a7b96e3ed00069d3d90.png