nanotrt

nanotrt
4小时前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
import java.util.Scanner;

class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; ++i) {
arr[i] = in.nextInt();
}
in.close();
System.out.println(minCost(arr));
}

private static int minCost(int[] arr) {
int n = arr.length;
int[][] dp = new int[n][n];
int[] preSum = new int[n + 1];
for (int i = 1; i <= n; ++i) {
preSum[i] = preSum[i - 1] + arr[i - 1];
}
for (int l = 1; l < n; ++l) {
for (int i = 0; i + l < n; ++i) {
int j = i + l, ans = Integer.MAX_VALUE;
for (int k = i; k < j; ++k) {
ans = Math.min(ans, dp[i][k] + dp[k + 1][j]);
}
dp[i][j] = ans + preSum[j + 1] - preSum[i];
}
}
return dp[0][n - 1];
}
}


nanotrt
4小时前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
import java.util.Scanner;

class Main {
private static int[] preSum;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; ++i) {
arr[i] = in.nextInt();
}
in.close();
int[][] dp = new int[n][n];
preSum = new int[n + 1];
for (int i = 1; i <= n; ++i) {
preSum[i] = preSum[i - 1] + arr[i - 1];
}
System.out.println(minCost(dp, arr, 0, n - 1));
}

private static int minCost(int[][] dp, int[] arr, int i, int j) {
if (i == j) return 0;
if (dp[i][j] != 0) return dp[i][j];
int ans = Integer.MAX_VALUE / 2;
for (int k = i; k < j; ++k) {
ans = Math.min(minCost(dp, arr, i, k) + minCost(dp, arr, k + 1, j), ans);
}
ans += preSum[j + 1] - preSum[i];
return dp[i][j] = ans;
}
}


nanotrt
2天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
import java.util.Scanner;
import java.util.Deque;
import java.util.ArrayDeque;

class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), k = in.nextInt();
int[] arr = new int[n + 1];
for (int i = 0; i < n; ++i) {
arr[i] = in.nextInt();
}
in.close();
solve(arr, n, k);
}

private static void solve(int[] arr, int n, int k) {
Deque<Integer> minQ = new ArrayDeque<>();
Deque<Integer> maxQ = new ArrayDeque<>();
StringBuilder minSb = new StringBuilder();
StringBuilder maxSb = new StringBuilder();
for (int i = 0; i < k; ++i) {
while (!minQ.isEmpty() && arr[minQ.peekLast()] > arr[i]) {
minQ.pollLast();
}
while (!maxQ.isEmpty() && arr[maxQ.peekLast()] < arr[i]) {
maxQ.pollLast();
}
minQ.offerLast(i);
maxQ.offerLast(i);
}

for (int i = k; i <= n; ++i) {
while (!minQ.isEmpty() && minQ.peekFirst() < i - k) {
minQ.pollFirst();
}
while (!maxQ.isEmpty() && maxQ.peekFirst() < i - k) {
maxQ.pollFirst();
}
minSb.append(arr[minQ.peekFirst()]);
minSb.append(" ");
maxSb.append(arr[maxQ.peekFirst()]);
maxSb.append(" ");
while (!minQ.isEmpty() && arr[minQ.peekLast()] > arr[i]) {
minQ.pollLast();
}
minQ.offerLast(i);
while (!maxQ.isEmpty() && arr[maxQ.peekLast()] < arr[i]) {
maxQ.pollLast();
}
maxQ.offerLast(i);
}
System.out.println(minSb);
System.out.println(maxSb);
}
}


Java太难了，挑战模式有点来不及啊

nanotrt
2天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
import java.util.Scanner;
import java.util.Deque;
import java.util.ArrayDeque;

class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int m = in.nextInt(), n = in.nextInt();
int[][] arr = new int[m][n + 1];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
arr[i][j] = in.next().equals("F") ? 1 : 0;
}
}
in.close();
System.out.println(3 * maxArea(arr, m, n));
}

private static int maxArea(int[][] arr, int m, int n) {
int[] maxHeight = new int[n + 1];
int ans = 0;
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < m; ++i) {
for (int j = 0; j <= n; ++j) {
maxHeight[j] = arr[i][j] == 0 ? 0 : 1 + maxHeight[j];
while (!stack.isEmpty() && maxHeight[stack.peek()] >= maxHeight[j]) {
int curHeight = maxHeight[stack.poll()];
int left = stack.isEmpty() ? -1 : stack.peek();
ans = Math.max((j - left - 1) * curHeight, ans);
}
stack.push(j);
}
stack.pop();
}
return ans;
}
}


nanotrt
5天前

算法

$O(logn)$

$a_n = a_{n - 1} + a_{n - 2}$
$a_{n - 1} = a_{n - 1}$

代码

blablabla
import java.util.Scanner;

class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n;
while ((n = in.nextInt()) != -1) {
System.out.println(fib(n));
}
in.close();
}

private static int fib(int n) {
if (n == 0) return 0;
int[][] A = new int[][]{{1, 1}, {1, 0}};
int[][] ret = new int[][]{{1, 0}, {0, 1}};
while (n > 0) {
if ((n & 1) == 1) {
ret = mul(ret, A);
}
A = mul(A, A);
n >>= 1;
}
return ret[1][0];
}

private static int[][] mul(int[][] A, int[][] B) {
int n = A.length;
int[][] ans = new int[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < n; ++k) {
ans[i][j] += A[i][k] * B[k][j];
}
ans[i][j] %= 10000;
}
}
return ans;
}
}


nanotrt
5天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
import java.util.Scanner;

class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n;
while ((n = in.nextInt()) != -1) {
System.out.println(fib(n));
}
in.close();
}

private static int fib(int n) {
if (n == 0) return 0;
int[][] A = new int[][]{{1, 1}, {1, 0}};
int[][] ret = new int[][]{{1, 0}, {0, 1}};
while (n > 0) {
if ((n & 1) == 1) {
ret = mul(ret, A);
}
A = mul(A, A);
n >>= 1;
}
return ret[1][0];
}

private static int[][] mul(int[][] A, int[][] B) {
int n = A.length;
int[][] ans = new int[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < n; ++k) {
ans[i][j] += A[i][k] * B[k][j];
}
ans[i][j] %= 10000;
}
}
return ans;
}
}


nanotrt
5天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
import java.util.Scanner;
import java.util.Deque;
import java.util.ArrayDeque;

class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.next();
System.out.println(maxLen(s));
}

private static int maxLen(String s) {
int ans = 0;
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1);
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
stack.push(i);
} else {
int j = stack.pop();
if (j != -1 && (s.charAt(i) == ')' && s.charAt(j) == '(' || s.charAt(i) == ']' && s.charAt(j) == '[' || s.charAt(i) == '}' && s.charAt(j) == '{')) {
ans = Math.max(ans, i - stack.peek());
} else {
stack.clear();
stack.push(i);
}
}
}
return ans;
}
}


nanotrt
5天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
import java.util.Scanner;
import java.util.PriorityQueue;

class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; ++i) {
arr[i] = in.nextInt();
}
in.close();
System.out.println(minCost(arr));
}

private static int minCost(int[] arr) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int a : arr) {
pq.offer(a);
}
int ans = 0;
while (pq.size() > 1) {
int a = pq.poll(), b = pq.poll();
ans += a + b;
pq.offer(a + b);
}
return ans;
}
}


nanotrt
5天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
import java.util.Scanner;
import java.util.Arrays;
import java.util.PriorityQueue;

class Main {
public static void main(String[] args) {
int[][] mat = new int[1000][2000];
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for (int i = 0; i < T; ++i) {
int m = in.nextInt(), n = in.nextInt();
for (int j = 0; j < m; ++j) {
for (int k = 0; k < n; ++k) {
mat[j][k] = in.nextInt();
}
}
solve(mat, m, n);
}
}

private static void solve(int[][] mat, int m, int n) {
int[] prev = mat[0];
Arrays.sort(prev, 0, n);
for (int i = 1; i < m; ++i) {
prev = merge(prev, mat[i], n);
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; ++i) {
sb.append(prev[i]);
sb.append(" ");
}
System.out.println(sb);
}

private static int[] merge(int[] prev, int[] cur, int n) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(prev[a[0]] + cur[a[1]], prev[b[0]] + cur[b[1]]));
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
pq.offer(new int[]{0, i});
}
for (int i = 0; i < n; ++i) {
int[] temp = pq.poll();
ans[i] = prev[temp[0]] + cur[temp[1]];
if (++temp[0] < n) {
pq.offer(temp);
}
}
return ans;
}
}


nanotrt
6天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
import java.util.Scanner;
import java.util.PriorityQueue;
import java.util.Arrays;

class Main {
public static void main(String[] args) {
int[][] arr = new int[10001][2];
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
for (int i = 0; i < n; ++i) {
arr[i][0] = in.nextInt();
arr[i][1] = in.nextInt();
}
System.out.println(maxProfit(arr, n));
}
in.close();
}

private static int maxProfit(int[][] arr, int n) {
Arrays.sort(arr, 0, n, (a, b) -> Integer.compare(a[1], b[1]));
PriorityQueue<Integer> pq = new PriorityQueue<>();
int ans = 0;
for (int i = 0; i < n; ++i) {
pq.offer(arr[i][0]);
if (pq.size() > arr[i][1]) {
pq.poll();
}
}
for (int a : pq) {
ans += a;
}
return ans;
}
}