本文主要是介绍hdoj 2372 El Dorado，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题号：hdoj 2372；链接：http://acm.hdu.edu.cn/showproblem.php?pid=2372
题目：
El Dorado
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 418 Accepted Submission(s): 197
Problem Description
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.
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.
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.
Input
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 a i (-10000 ≤ a i ≤ 10000 ), where a iis the i th number in the sequence drawn by the machine.
The last test case is followed by a line containing two zeros.
The last test case is followed by a line containing two zeros.
Output
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 .
Sample Input
10 5 1 2 3 4 5 6 7 8 9 10 3 2 3 2 1 0 0
Sample Output
252 0
题目要求一个序列中长度为k的递增子序列的个数，我们可以用dp来做。dp[i][j]的含义：i表示子序列中尾元素的下标，j表示子序列的长度。这样的话，我们可以得到状态转移方程:dp[i][j] = sum(dp[k][j-1]) 其中(a[k]< a[i])(k>=j-1&&k<i),最后，我们所要求的结果就是sum（dp[i][k]）(i=1,2,...,n).
代码：
#include <iostream>
#include <cstring>
using namespace std;const int MAXN = 110;
__int64 dp[MAXN][MAXN];
int a[MAXN];int main()
{std::ios::sync_with_stdio(false);int n, k;while(!cin.eof()){long long ans = 0;cin >> n >> k;if(0 == n && 0 == k) break;for(int i = 1; i <= n; i++)cin >> a[i]; memset(dp, 0, sizeof(dp));for(int i = 1; i <= n; i++)dp[i][1] = 1;for(int j = 2; j <= k; j++){for(int i = j; i <= n; i++){for(int m = j - 1; m < i; m++){if(a[i] > a[m]){dp[i][j] += dp[m][j-1];}}}}for(int i = 1; i <= n; i++)ans += dp[i][k];cout << ans << endl;}return 0;
}
这篇关于hdoj 2372 El Dorado的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
