2017 百度

一个数轴上共有N个点，第一个点的坐标是度度熊现在位置，第N-1个点是度度熊的家。现在他需要依次的从0号坐标走到N-1号坐标。 但是除了0号坐标和N-1号坐标，他可以在其余的N-2个坐标中选出一个点，并直接将这个点忽略掉，问度度熊回家至少走多少距离？

输入描述:

输入一个正整数N, N <= 50。 接下来N个整数表示坐标，正数表示X轴的正方向，负数表示X轴的负方向。绝对值小于等于100

输出描述:

输出一个整数表示度度熊最少需要走的距离。 示例1

输入

4 1 4 -1 3

输出

4

思路：

public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] a = new int[n]; for(int i=0; i<n; i++) a[i]=sc.nextInt(); int sum = 0, max = 0; for(int i=1; i<a.length; i++) sum += Math.abs(a[i] - a[i-1]); for(int i=1; i<n-1; i++) { int t = Math.abs(a[i-1]-a[i]) + Math.abs(a[i]-a[i+1]) - Math.abs(a[i-1]-a[i+1]); max = Math.max(max, t); } System.out.println(sum - max); } }

三维空间中有N个点，每个点可能是三种颜色的其中之一，三种颜色分别是红绿蓝，分别用'R', 'G', 'B'表示。 现在要找出三个点，并组成一个三角形，使得这个三角形的面积最大。 但是三角形必须满足：三个点的颜色要么全部相同，要么全部不同。

输入描述:

首先输入一个正整数N三维坐标系内的点的个数.(N <= 50) 接下来N行，每一行输入 c x y z，c为'R', 'G', 'B' 的其中一个。x，y，z是该点的坐标。(坐标均是0到999之间的整数)

输出描述:

输出一个数表示最大的三角形面积，保留5位小数。 示例1

输入

5 R 0 0 0 R 0 4 0 R 0 0 3 G 92 14 7 G 12 16 8

输出

6.00000

思路：计算三角形面积 (海伦公式 

doublea = L3(i, j); doubleb = L3(i, k); doublec = L3(k, j); doublep = (a + b + c) / 2; return sqrt(p * (p - a) * (p - b) * (p - c));    

度度熊有一个N个数的数组，他想将数组从小到大 排好序，但是萌萌的度度熊只会下面这个操作： 任取数组中的一个数然后将它放置在数组的最后一个位置。 问最少操作多少次可以使得数组从小到大有序？

输入描述:

首先输入一个正整数N，接下来的一行输入N个整数。(N <= 50, 每个数的绝对值小于等于1000)

输出描述:

输出一个整数表示最少的操作次数。 示例1

输入

4 19 7 8 25

输出

2

思路：找到按照排序后从最小值开始的最长的长度

package l4; import java.util.Arrays; import java.util.Scanner; /* * 找到按照排序后最长的长度 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] a = new int[n]; for(int i=0; i<n; i++) a[i]=sc.nextInt(); int[] b = Arrays.copyOf(a, a.length); Arrays.sort(a); int i = 0, j = 0; for(; j<n; j++) { while(i<n && b[i]!=a[j]) i++; if(i == n) break; i ++; } System.out.println(n-j); } }

链接：https://www.nowcoder.com/questionTerminal/621e433919214a9ba46087dd50f09879 来源：牛客网 度度熊最近对全排列特别感兴趣,对于1到n的一个排列,度度熊发现可以在中间根据大小关系插入合适的大于和小于符号(即 '>' 和 '<' )使其成为一个合法的不等式数列。但是现在度度熊手中只有k个小于符号即('<'')和n-k-1个大于符号(即'>'),度度熊想知道对于1至n任意的排列中有多少个排列可以使用这些符号使其为合法的不等式数列。

输入描述:

输入包括一行,包含两个整数n和k(k < n ≤ 1000)

输出描述:

输出满足条件的排列数,答案对2017取模。 示例1

输入

5 2

输出

66

刚开始DFS，TLE

package l5; import java.util.Scanner; public class TLE { static int cnt = 0; static boolean[] b; static int[] a; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), k = sc.nextInt(); b = new boolean[n]; a = new int[n]; dfs(0, n, k); System.out.println(cnt 17); } private static void dfs(int s, int n, int k) { if(s == n) { int smaller = 0; for(int i=1; i<n; i++) { if(a[i-1] < a[i]) { smaller ++; if(smaller > k) return; } } if(smaller == k) cnt ++; return; } for(int i=0; i<n; i++) { if(!b[i]) { b[i] = true; a[s] = i; dfs(s+1, n, k); b[i] = false; } } } } 改为DP  * dp[i][j]表示1..i有j个小于号  * 通过将第i+1插入到之前弄好的数组来建立dp[i+1]与dp[i]的关系  * 这样插入生成的数列不会多余，也不会重复

package l5; import java.util.Scanner; /* * DP * dp[i][j]表示1..i有j个小于号 * 通过将第i+1插入到之前弄好的数组来建立dp[i+1]与dp[i]的关系 * 这样插入生成的数列不会多余，也不会重复 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), k = sc.nextInt(); long[][] dp = new long[1+n][1+k]; dp[2][0] = 1; dp[2][1] = 1; for(int i=3; i<=n ; i++) { dp[i][0] = 1; for(int j=1; j<=k; j++) { dp[i][j] = dp[i-1][j-1] * (i-j-1 + 1) + dp[i-1][j] * (j + 1); dp[i][j] %= 2017; } } System.out.println(dp[n][k] % 2017); } }