点击打开题目链接
下面是别处找来的中文翻译版
【问题描述】 “逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者，就要遵守这条秘诀:"逢低吸纳,越低越买"这句话的意思是：每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好，看看你最多能按这个规则买几次。 给定连续的N天中每天的股价。你可以在任何一天购买一次股票，但是购买时的股价一定要比你上次购买时的股价低。写一个程序，求出最多能买几次股票。 以下面这个表为例, 某几天的股价是: 天数1 2 3 4 5 6 7 8 9 10 11 12 股价68 69 54 64 68 64 70 67 78 62 98 87 这个例子中, 聪明的投资者(按上面的定义)，如果每次买股票时的股价都比上一次买时低，那么他最多能买4次股票。一种买法如下(可能有其他的买法): 天数2 5 6 10 股价69 68 64 62 【输入文件】buylow.in 第1行: N (1 <= N <= 5000), 表示能买股票的天数。 第2行以下: N个正整数 (可能分多行) ，第i个正整数表示第i天的股价. 这些正整数大小不会超过longint(pascal)/long(c++). 【输出文件】buylow.out 只有一行，输出两个整数： 能够买进股票的天数 长度达到这个值的股票购买方案数量 在计算解的数量的时候，如果两个解所组成的字符串相同，那么这样的两个解被认为是相同的（只能算做一个解）。因此，两个不同的购买方案可能产生同一个字符串，这样只能计算一次。 【输入样例】 12 68 69 54 64 68 64 70 67 78 62 98 87 【输出样例】 4 2
第一问求解比较简单，直接O(n^2)求最长下降子序列长度dp算法套就行了,即dp[i]=max{dp[i],dp[j]+1} (arr[j]>arr[i])
第二问求解，先要把dp[i]求出，在此基础上可用cnt[i]表示第i天买股票情况下，长度达到前i天买进股票的天数
这个值的股票购买方案数量（总之仅考虑前i天），则cnt[i]=cnt[i]+cnt[k](其中dp[k]+1=dp[i])(而dp[i]=1时可特殊考虑，
直接令cnt[i]=1)。但是上面这样会有重复情况出现，cnt[i]会多算。细想就会发现，这些情况是出现在股价arr[k1]=arr[k2](不妨设k1<k2)下。
所以，倒着扫过来，如果一个数已经被扫过，就要用布尔数组标记下，之后再出现该数，判断，做到防重。
具体去重操作还需一些技巧，整道题代码如下：
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.util.HashMap; import java.util.StringTokenizer; class Reader { static BufferedReader reader; static StringTokenizer tokenizer; static void init(InputStream input) { reader = new BufferedReader(new InputStreamReader(input)); tokenizer = new StringTokenizer(""); } static String next() throws IOException { while (!tokenizer.hasMoreTokens()) { tokenizer = new StringTokenizer(reader.readLine()); } return tokenizer.nextToken(); } static int nextInt() throws IOException { return Integer.parseInt(next()); } } public class Main { /** * @param args */ static long ans; static int n, max; static int arr[], f[], pre[]; static boolean bo[]; static long cnt[]; static HashMap<Integer, Integer> hashMap; public static void main(String[] args) throws IOException { // TODO Auto-generated method stub Reader.init(System.in); n = Reader.nextInt(); arr = new int[n + 1]; pre = new int[n + 1]; cnt = new long[n + 1]; f = new int[n + 1]; cnt = new long[n + 1]; for (int i = 1; i <= n; i++) arr[i] = Reader.nextInt(); hashMap = new HashMap<Integer, Integer>(); for (int i = 1; i <= n; i++) if (!hashMap.containsKey(arr[i])) { hashMap.put(arr[i], i); } else { pre[i] = hashMap.get(arr[i]); hashMap.put(arr[i], i); } f[1] = 1; cnt[1] = 1; for (int i = 2; i <= n; i++) { f[i] = 1; bo = new boolean[i + 1]; for (int j = i - 1; j >= 1; j--) if ((arr[j] > arr[i]) && (f[j] + 1 > f[i])) f[i] = f[j] + 1; cnt[i] = 0; if (f[i] == 1) cnt[i] = 1; else { for (int j = i - 1; j >= 1; j--) { if ((!bo[j]) && (f[j] + 1 == f[i]) && (arr[j] > arr[i])) cnt[i] = cnt[i] + cnt[j]; bo[pre[j]] = true; } } } max = 0; for (int i = 1; i <= n; i++) if (f[i] > max) max = f[i]; ans = 0; bo = new boolean[n + 1]; for (int i = n; i >= 1; i--) { if ((!bo[i]) && (f[i] == max)) ans = ans + cnt[i]; bo[pre[i]] = true; } System.out.println(max + " " + ans); } }
