目录
- 前言
- 一、滚球游戏
- 代码：DP
- 二、数列变换（调试了一个小时A了9%，盖了帽了 print（3 4）就是9%）
- 代码：常规
前言
如果你从本文中学习到丝毫知识，那么请您点点关注、点赞、评论和收藏
大家好，我是爱做梦的鱼，我是东北大学大数据实验班大三的小菜鸡，非常渴望优秀，羡慕优秀的人，个人博客为：爱做梦的鱼https://zihao.blog.csdn.net/，微信公众号、微信视频号为【程序猿干货铺】，qq交流群为：1107710098，
一、滚球游戏
时间限制： 3000MS
内存限制： 589824KB
题目描述：
某滚球游戏规则如下：球从入口处（第一层）开始向下滚动，每次可向下滚动一层，直到滚至最下面一层为止。球每次可滚至左下、下方或右下三个方格中的任意一个，每个方格都有一个得分，如下图所示。第1层有1个方格，第2层有3个方格，……，以此类推，第n层有2*n-1个方格。设计一个算法，使得球从入口滚至最下面一层的总得分和最大。
代码：DP
import java.util.Scanner;
public class First {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int row = sc.nextInt();
int col = 2 * row - 1;
int[][] matrix = new int[row][col];
int beginRow = 0; //起始行
int beginCol = row - 1; //每行的起始列
sc.nextLine(); //从下一行开始
while (sc.hasNextLine()) {
String[] line = sc.nextLine().split(" ");
int c = beginCol;
for (String num : line) {
if (!("".equals(num))) { //过滤空格
matrix[beginRow][c] = Integer.parseInt(num);
c++;
}
}
beginRow++;
beginCol--;
}
//从下往上加
for (int i = row - 2; i >= 0; i--) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] != 0) {
matrix[i][j] += Math.max(matrix[i + 1][j - 1], Math.max(matrix[i + 1][j], matrix[i + 1][j + 1])); //每个位置的元素为当前值+左下、下、右下的最大值
}
}
}
System.out.println(matrix[0][row - 1]); //结果为第一行的元素
}
}
输入描述
第1行的正整数n表示数字三角形的层数。（n<=100)
接下来n行包含一个数字三角形，每一行包含2n-1个方格，对应有2n-1个表示得分的正整数（不超过10^5），每两个数字之间用空格隔开。
输出描述
球从入口（第一层）滚至最下面一层的最大得分和。
样例输入
3
1
2 1 2
3 4 2 1 3
样例输出
7
import java.util.Scanner;
public class First {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int row = sc.nextInt();
int col = 2 * row - 1;
int[][] matrix = new int[row][col];
int beginRow = 0; //起始行
int beginCol = row - 1; //每行的起始列
sc.nextLine(); //从下一行开始
while (sc.hasNextLine()) {
String[] line = sc.nextLine().split(" ");
int c = beginCol;
for (String num : line) {
if (!("".equals(num))) { //过滤空格
matrix[beginRow][c] = Integer.parseInt(num);
c++;
}
}
beginRow++;
beginCol--;
}
//从下往上加
for (int i = row - 2; i >= 0; i--) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] != 0) {
matrix[i][j] += Math.max(matrix[i + 1][j - 1], Math.max(matrix[i + 1][j], matrix[i + 1][j + 1])); //每个位置的元素为当前值+左下、下、右下的最大值
}
}
}
System.out.println(matrix[0][row - 1]); //结果为第一行的元素
}
}
二、数列变换（调试了一个小时A了9%，盖了帽了 print（3 4）就是9%）
时间限制： 5000MS
内存限制： 655360KB
题目描述：
有一个初始长度为0的数列，现在对其实施以下三种操作：
(1) 插入某一个元素；
(2) 将某一个元素删除；
(3) 查询当前数列的状态（输出数列中每一个元素的值）。
输入描述
单组输入。
第1行一个正整数m表示一共有m个操作。
接下来m行表示m个操作，每行输入的第1个数字为op（操作类型）。
如果op=1表示第(1)种操作，后面接着两个数字a和b分别表示在第a个位置插入b（a以及a以后的数字将后移）。
如果op=2表示第(2)种操作，后面接着一个数字a，表示删除第a个数字。
如果op=3表示第(3)种操作，查询当前数列的状态。
（m<=1000，输入操作保证合法。）
输出描述
对于每一个op=3，输出当前数列的状态（输出数列中每一个元素的值）。
样例输入
3
1 1 3
1 2 4
3
样例输出
3 4
代码：常规
import java.util.LinkedList;
import java.util.Scanner;
public class Second {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
// ArrayList<Integer> list = new ArrayList<Integer>();
LinkedList<Integer> list = new LinkedList<Integer>();
for (int i = 0; i < m; i++) {
int op = sc.nextInt();
if (op == 1) {
int index = sc.nextInt();
int num = sc.nextInt();
list.add(index - 1, num);
} else if (op == 2) {
int index = sc.nextInt();
if (index <= list.size()) {
list.remove(index - 1);
}
} else if (op == 3) {
for (int num : list) {
System.out.print(num + " ");
}
}
}
sc.close();
}
}
