07-独立的小易-堆棋子-疯狂队列-小易喜欢的数列-戳气球
年轻即出发...
简书：https://www.jianshu.com/u/7110a2ba6f9e
知乎：https://www.zhihu.com/people/zqtao23/posts
GitHub源码：https://github.com/zqtao2332
个人网站：http://www.zqtaotao.cn/ （停止维护更新内容）
QQ交流群：606939954
咆哮怪兽一枚...嗷嗷嗷...趁你现在还有时间，尽你自己最大的努力。努力做成你最想做的那件事，成为你最想成为的那种人，过着你最想过的那种生活。也许我们始终都只是一个小人物，但这并不妨碍我们选择用什么样的方式活下去，这个世界永远比你想的要更精彩。
最后：喜欢编程，对生活充满激情
本节内容预告
实例1：独立的小易
实例2：堆棋子
实例3：疯狂队列
实例4：小易喜欢的数列
实例5：戳气球
实例1：独立的小易
独立的小易时间限制: 1秒空间限制: 32768K小易为了向他的父母表现他已经长大独立了,他决定搬出去自己居住一段时间。一个人生活增加了许多花费:小易每天必须吃个水果并且需要每天支付x元的房屋租金。当前小易手中已经有f个水果和d元钱,小易也能去商店购买一些水果,商店每个水果售卖p元。小易为了表现他独立生活的能力,希望能独立生活的时间越长越好,小易希望你来帮他计算一下他最多能独立生活多少天。
输入描述:输入包括一行,四个整数x, f, d, p
输入例子1:
35 100 10
输出例子1:
11
public class Code_20_MaxLiveDay {
/**
* @param x 每天需要支付的房租
* @param f 手里已经有的水果数
* @param d 拥有的钱
* @param p 每个水果售价
*/
public static int liveDay(int x, int f, int d, int p) {
// 在水果够吃的情况下，唯一的开销是房租
if (f >= (d / x)) {
return d / x;
}
return f + (d - f * x) / (p + x);
}
public static void main(String[] args) {
System.out.println(liveDay(3, 5, 100, 10));
}
}
实例2：堆棋子
堆棋子时间限制: 1秒空限制: 32768K
小易将n个棋子摆放在一张无限大的棋盘上。第个棋子放在第x[i]行 y[i]列。同一个格子允许放置多个棋子。每一次操作小易可以把一个棋子拿起并将其移动到原格子的上、下、左、右的任意一个格子中。小易想知道要让棋盘上出现有一个格子中至少有i (1 <= i <=n ) 个棋子所需要的最少操作次数。
输入描述:输入包括三行,第一行一个整数n(1 <= n <= 50),表示棋子的个数
第二行为n个棋子的横坐标x[i] (1 <= n <= 10^9)
第三行为n个棋子的横坐标y[i] (1 <= n <= 10^9)
输出描述:
输出n个整数,第i个表示棋盘上有一个格子至少有i个棋子所需要的操作数,以空格分割。
行末无空格如样例所示:对于1个棋子:不需要操作
对于2个棋子:将前两个棋子放在(1, 1)中
对于3个棋子:将前三个棋子放在(2, 1)中
对于4个棋子:将所有棋子都放在(3, 1)中
输入例子1:
4
1 2 4 9
1 1 1 1
输出例子1:
0 1 3 10
曼哈顿距离
曼哈顿距离：两个点之间行走的最小距离
2_1_曼哈顿距离.png
想要操作数最小，需要将其他的点移动到一个M点，这个M点距离其他点的曼哈顿距离最小。
2_2_多点之间曼哈顿距离.png
对于这个点的选取规则，
假设有四个点，那么尝试出那个最短点需要尝试16次。尝试点的横坐标来着输入点的横坐标集合，同理纵坐标。
每次使用这个选择点来分别和四个输入点来进行曼哈顿最小距离计算。
2_3_曼哈顿最短点选取.png
import java.util.PriorityQueue;
import java.util.Scanner;
public class Code_21_MinOPS {
/**
* @param size 点个数
* @param x 横坐标
* @param y 纵坐标
*/
public static int[] minOPs(int size, int[] x, int[] y) {
int[] res = new int[size];
for (int i = 0; i < size; i++) { // 结果数组初始化
res[i] = Integer.MAX_VALUE;
}
// 优先级队列：存储穷举的各个点到输入点的曼哈顿距离
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) { // 两个for用来穷举所有可能作为到输入点曼哈顿距离最小的点
for (int k = 0; k < size; k++) { // 每次和输入的size个点进行曼哈顿距离计算
pq.add(Math.abs(x[k] - x[i]) + Math.abs(y[k] - y[j]));
}
int resIndex = 0;
int sum = 0; // i个点移动到当前穷举的可能点的曼哈顿距离
// （x[i],y[i]）这个可能点，存在 i 个点的曼哈顿距离（操作数）
while (!pq.isEmpty()) {
sum += pq.poll();
res[resIndex] = Math.min(res[resIndex], sum);
resIndex++;
}
}
}
return res;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int size = in.nextInt();
int[] x = new int[size];
int[] y = new int[size];
for (int i = 0; i < size; i++) {
x[i] = in.nextInt();
}
for (int i = 0; i < size; i++) {
y[i] = in.nextInt();
}
int[] res = minOPs(size, x, y);
StringBuilder result = new StringBuilder();
for (int i = 0; i < size; i++) {
result.append(String.valueOf(res[i]) + " ");
}
System.out.println(result.toString().trim());
}
in.close();
}
}
实例3：疯狂队列
疯狂队列时间限制: 1秒限制: 32768K小易老师是非常严厉的,它会要求所有学生在进入教室前都排成一列,并且他要求学生按照身高不递减的顺序排列。有一次,n个学生在列队的时候,小易老师正好去卫生间了。学生们终于有机会反击了,于是学生们决定来一次疯狂的队列,他们定义一个队列的疯狂值为每对相邻排列学生身高差的绝对值总和。由于按照身高顺序排列的队列的疯狂值是最小的,他们当然决定按照疯狂值最大的顺序来进行列队。现在给出n个学生的身高,请计算出这些学生列队的最大可能的疯狂值。小易老师回来一定会气得半死。
输入描述:输入包括两行,第一行一个整数n (1 <= n <= 50),表示学生的人数第二行为n个整数h[i] (1 <= h[i] <= 1000),表示每个学生的身高
输出描述:输出一个整数,表示n个学生列队可以获得的最大的疯狂值。
例如
输入
5
5 10 25 40 25
输出： 100
最大疯狂值时，队列顺序是25-10-40-5-25
贪心策略：
先选出最大和最小站好，次大放在最小右边，次小放在最大左边
import java.util.Arrays;
import java.util.Scanner;
public class Code_22_MaxMad {
/**
*
* 贪心策略：先选出最大和最小站好，次大放在最小右边，次小放在最大左边
*
* 通过坐标变化模拟站队
*
* 1 20 50 200
* 第一步模拟：200 1 选出最大和最小
* 第二步模拟：200 1 50 次大放最小右边
* 第三步模拟：20 200 1 50 次小放最大左边
*
* 如果是奇数个，最后一个需要判断放左边还是放右边
*/
public static int maxMad(int[] arr) {
Arrays.sort(arr);
int res = arr[arr.length - 1] - arr[0];
int maxI = arr.length - 2; // 次大下标
int minI = 1; // 次小下标
while (minI < maxI) {
res += arr[maxI + 1] - arr[minI];
res += arr[maxI] - arr[minI - 1];
maxI--;
minI++;
}
if (minI == maxI) { // 奇数个处理
res += Math.max(arr[minI] - arr[minI - 1], arr[minI + 1] - arr[minI]);
}
return res;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}
System.out.println(maxMad(arr));
}
in.close();
}
}
实例4：小易喜欢的数列
小易喜欢的数列时间限制: 1秒间限制: 32768K
小易非常喜欢拥有以下性质的数列:
1、数列的长度为n
2、数列中的每个数都在1到k之间(包括1和k)
3、对于位置相邻的两个数A和B (A在B前),都满足(A <= B)或(A mod B != 0)(满足其一即可)
例如,当n=4, k=7
那么(1, 7, 7,2],它的长度是4,所有数字也在1到7范围内,并且满足第三条性质,所以小易是喜欢这个数列的
但是小易不喜欢[4, 4,4, 2]这个数列。小易给出n和k,希望你能帮他求出有多少个是他会喜欢的数列。
import java.util.Scanner;
public class Code_23_LikeSequence {
// 暴力尝试
public static long number1(int n, int k) {
return process(1, n, k);
}
public static long process(int pre, int n, int k) {
if (n == 0) {
return 1L;
}
long sum = 0;
for (int cur = pre; cur <= k; cur++) {
sum += process(cur, n - 1, k);
}
for (int cur = 1; cur < pre; cur++) {
sum += (pre % cur) != 0 ? process(cur, n - 1, k) : 0;
}
return sum % 1000000007L;
}
// 动态规划
public static long number2(int n, int k) {
long[][] dp = new long[k + 1][n];
for (int i = 0; i < k + 1; i++) {
dp[i][0] = 1L;
}
for (int col = 1; col < n; col++) {
for (int row = 1; row < k + 1; row++) {
long sum = 0L;
for (int cur = row; cur <= k; cur++) {
sum += dp[cur][col - 1];
}
for (int cur = 1; cur < row; cur++) {
sum += (row % cur) != 0 ? dp[cur][col - 1] : 0;
}
dp[row][col] = sum % 1000000007L;
}
}
long res = 0L;
for (int i = 1; i <= k; i++) {
res += dp[i][n - 1];
res %= 1000000007L;
}
return res;
}
// 动态规划进一步缩减计算量
public static long number3(int n, int k) {
long[][] dp = new long[k + 1][n];
for (int i = 0; i < k + 1; i++) {
dp[i][0] = 1L;
}
for (int col = 1; col < n; col++) {
long sum = 0;
for (int row = 1; row < k + 1; row++) {
sum += dp[row][col - 1];
sum %= 1000000007L;
}
for (int row = 1; row < k + 1; row++) {
long noInclude = 0L;
for (int cur = row * 2; cur <= k; cur += row) {
noInclude += dp[cur][col - 1];
noInclude %= 1000000007L;
}
dp[row][col] = (sum - noInclude) % 1000000007L;
}
}
long res = 0L;
for (int i = 1; i <= k; i++) {
res += dp[i][n - 1];
res %= 1000000007L;
}
return res;
}
// 缩减空间
public static long number4(int n, int k) {
long[] dp = new long[k + 1];
for (int i = 0; i < k + 1; i++) {
dp[i] = 1L;
}
for (int col = 1; col < n; col++) {
long sum = 0;
for (int row = 1; row < k + 1; row++) {
sum += dp[row];
sum %= 1000000007L;
}
for (int row = 1; row < k + 1; row++) {
long noInclude = 0L;
for (int cur = row * 2; cur <= k; cur += row) {
noInclude += dp[cur];
noInclude %= 1000000007L;
}
dp[row] = (sum - noInclude) % 1000000007L;
}
}
long res = 0L;
for (int i = 1; i <= k; i++) {
res += dp[i];
res %= 1000000007L;
}
return res;
}
public static void main(String[] args) {
System.out.println(number1(6, 9));
System.out.println(number2(6, 9));
System.out.println(number3(6, 9));
System.out.println(number4(6, 9));
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int n = in.nextInt();
int k = in.nextInt();
System.out.println(number2(n, k));
}
in.close();
}
}
实例5：戳气球
有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。每当你戳破一个气球 i 时，你可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。
说明:
你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
示例:
输入: [3,1,5,8]
输出: 167
解释:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
public class Code_24_MaxCoins {
// 暴力尝试
public static int maxCoins1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
if (arr.length == 1) {
return arr[0];
}
int[] help = new int[arr.length + 2];
help[0] = 1;
help[help.length - 1] = 1;
for (int i = 0; i < arr.length; i++) {
help[i + 1] = arr[i];
}
return process(help, 1, help.length - 2);
}
// 尝试最后打的位置获得的收益
// 不尝试以某个位置第一个打获得的最大收益
// 尝试以某一个位置为最后一个打，获得的最大收益，
// 把每一个位置都作为最后一个打掉的位置尝试一遍就是解
public static int process(int[] arr, int l, int r) {
if (l == r) { // 这个范围只有一个数
return arr[l - 1] * arr[l] * arr[r + 1];
}
// 尝试，最后打L 获得的收益，最后打L+1获得的收益...最后打R获得的收益
// 这些收益中最大的，就是L到R范围上收益最大的
int max = Math.max(
arr[l - 1] * arr[l] * arr[r + 1] + process(arr, l + 1, r), // 最后打L
arr[l - 1] * arr[r] * arr[r + 1] + process(arr, l, r - 1)); // 最后打R，两者取最大
// 尝试中间作为最后打掉获得的最大收益
// L~i~R 尝试i是最后一个打掉的
// 那么收益是 L~i-1 范围最大收益 + i+1~R上最大收益 + i 位置收益
for (int i = l + 1; i < r; i++) {
max = Math.max(
max,
arr[l - 1] * arr[i] * arr[r + 1] // i 位置收益
+ process(arr, l, i - 1) // L~i-1 范围收益
+ process(arr, i + 1, r)); // i+1~R 范围收益
}
return max;
}
public static int maxCoins2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int size = arr.length;
int[] all = new int[size + 2];
all[0] = 1;
all[size + 1] = 1;
for (int i = 0; i < size; i++) {
all[i + 1] = arr[i];
}
int[][] dp = new int[size][size];
for (int row = size - 1; row >= 0; row--) {
dp[row][row] = all[row] * all[row + 1] * all[row + 2];// base case
for (int col = row + 1; col < size; col++) {
int coins = 0;
for (int k = row; k <= col; k++) { // 以 i 位置为最后一个打的最大收益
coins = all[row] * all[k + 1] * all[col + 2];
coins += k != row ? dp[row][k - 1] : 0; // 依赖左边一行
coins += k != col ? dp[k + 1][col] : 0; // 依赖下边一列
dp[row][col] = Math.max(dp[row][col], coins);
/*
就是暴力递归里面的 以 i 位置为最后一个获得的收益
max = Math.max(
max,
arr[l - 1] * arr[i] * arr[r + 1] // i 位置收益
+ process(arr, l, i - 1) // L~i-1 范围收益
+ process(arr, i + 1, r)); // i+1~R 范围收益
*/
}
}
}
return dp[0][size - 1];
}
public static void main(String[] args) {
int[] arr = { 3, 2, 6, 4, 2, 7, 4, 7, 9 };
System.out.println(maxCoins1(arr));
System.out.println(maxCoins2(arr));
}
}
