速度提高了一倍啊,看来底层的东西还是有必要了解的,不过Java写东西是真方便啊
本来这道题是要高精度的,YD啊,但是Java有BigDecimal,哈哈,不过这玩意好用是好用,但是确实是非常的慢
我估计我自己用一个数组实现的话,速度应该还会快的
不过最后被我瞎猫碰死耗子碰到了,终于过了。
1 import java.io.*;
2 import java.math.BigInteger;
3 import java.util.*;
4 /*
5 ID: yanglei4
6 LANG: JAVA
7 TASK:buylow
8 */
9 public class buylow{
10 public static void main(String[] args) throws IOException {
11 BufferedReader f = new BufferedReader(new FileReader("buylow.in"));
12 PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("buylow.out")));
13 int N = Integer.parseInt(f.readLine());
14 int[] D = new int[N];
15 int count = 0;
16 String temp = f.readLine();
17 while (temp != null) {
18 StringTokenizer st = new StringTokenizer(temp);
19 int len = st.countTokens();
20 for (int i = 0; i < len; i++)
21 D[count++] = Integer.parseInt(st.nextToken());
22 temp = f.readLine();
23 }
24 long[] lds = new long[N];
25 BigInteger[] cnt = new BigInteger[N];
26 for (int i = 0; i < N; i++) {
27 lds[i] = 1;
28 cnt[i] = new BigInteger("1");
29 }
30 ArrayList<Integer> exist = new ArrayList<Integer>();
31 for (int i = 0; i < N; i++) {
32
33 for (int j = i - 1; j >= 0; j--) {
34 if (D[i] < D[j]) {
35 if (lds[j] + 1 > lds[i]) {
36 lds[i] = lds[j] + 1;
37 exist.clear();
38 exist.add(D[j]);
39 cnt[i] = new BigInteger(cnt[j].toByteArray());
40 }
41 else if (lds[j] + 1 == lds[i]) {
42 if (!exist.contains(D[j])) {
43 exist.add(D[j]);
44 cnt[i] = cnt[i].add(cnt[j]);
45 }
46 }
47
48 }
49 }
50 }
51
52 /* for (int i = 0; i < N; i++)
53 System.out.println(lds[i][0] + " " + lds[i][1] + " " + cnt[i]);*/
54
55 long maxleng = 0;
56 for (int i = 0; i < N; i++) {
57 if (maxleng < lds[i])
58 maxleng = lds[i];
59 }
60 BigInteger sum = new BigInteger("0");
61 exist = new ArrayList<Integer>();
62 for (int i = N - 1; i >= 0; i--) {
63 if (lds[i] == maxleng)
64 if (!exist.contains(D[i])) {
65 sum = sum.add(cnt[i]);
66 exist.add(D[i]);
67 }
68 }
69
70 out.println(maxleng + " " + sum);
71 out.close();
72 System.exit(0);
73 }
74 }
75
就是红色的那个地方,用toString的话,最后一个点过不了,换成了这个就过了。