El Dorado
Time Limit: 1000MS Memory limit: 65536K
题目描述
Bruce Force has gone to Las Vegas, the El Dorado for gamblers. He is interested especially in one betting game, where a machine forms a sequence of n numbers by drawing random numbers. Each player should estimate beforehand, how many increasing subsequences of length k will exist in the sequence of numbers.
A subsequence of a sequence a1, ..., an is defined as ai1, ..., ail, where 1 ≤ i1 < i2 < ... < il ≤ n. The subsequence is increasing, if aij-1 < aij for all 1 < j ≤ l.
Bruce doesn\'t trust the Casino to count the number of increasing subsequences of length k correctly. He has asked you if you can solve this problem for him.
输入
The input contains several test cases. The first line of each test case contains two numbers n and k (1 ≤ k ≤ n ≤ 100), where n is the length of the sequence drawn by the machine, and k is the desired length of the increasing subsequences. The following line contains n pairwise distinct integers ai (-10000 ≤ ai ≤ 10000 ), where ai is the ithnumber in the sequence drawn by the machine.
The last test case is followed by a line containing two zeros.
输出
For each test case, print one line with the number of increasing subsequences of length k that the input sequence contains. You may assume that the inputs are chosen in such a way that this number fits into a 64 bit signed integer (in C/C++, you may use the data type "long long", in Java the data type "long").
示例输入
10 5 1 2 3 4 5 6 7 8 9 10 3 2 3 2 1 0 0
示例输出
252 0
原来这道题是dp，亏我以前还花这么多时间做dp，妹的！感觉有必要系统的搞下dp的理论了，改天看看黑书。
dp[i][j] 表示以num[i]为结尾的，序列长度为j的情况数。
转移方程 dp[i][j] = sum(dp[k][j-1]) ; 前提：num[i] > num[k];
ans = sum(dp[i][m]); i = 0, 1, 2, ....n-1;