HDU2372ElDorado（DP）的最长上升子序列长度求解方法

1 #include
2 #include <string.h>
3 #define LL __int64
4
5 int n, m;
6 int a[110];
7 LL dp[110][110];
8
9 void Solve()
10 {
11 while(~scanf("%d%d", &n, &m))
12 {
13 memset(dp, 0, sizeof(dp));
14 if(!n && !m)
15 {
16 break;
17 }
18 for(int i = 0; i i)
19 {
20 scanf("%d", &a[i]);
21 }
22 for(int i = 0; i i)
23 {
24 dp[i][1] = 1;
25 }
26 for(int j = 2; j <= m; ++j)
27 {
28 for(int i = j-1; i i)
29 {
30 for(int k = j-2; k k)
31 {
32 if(a[i] > a[k])
33 {
34 dp[i][j] += dp[k][j-1];
35 }
36 }
37 }
38 }
39 LL sum = 0;
40 for(int i = m-1; i i)
41 {
42 sum += dp[i][m];
43 }
44 printf("%I64d\n", sum);
45 }
46 }
47
48 int main()
49 {
50 Solve();
51
52 return 0;
53 }