El Dorado(dp)

http://acm.hdu.edu.cn/showproblem.php?pid=2372

题意：给出n个数，求长度为m的递增子序列的数目。

思路：状态转移方程 dp[i][j] = sum(dp[k][j-1]| k < i &&a[k]<a[i])  表示前i个元素中长度为j的递增子序列的数目

#include <stdio.h>
#include <string.h>
const int N=120;
__int64 dp[N][N];
__int64 a[N];
int main()
{
    __int64 n,m;
    while(~scanf("%I64d%I64d",&n,&m))
    {
        if (n==0&&m==0)
            break;
        memset(dp,0,sizeof(dp));
        for (int i = 1;i <= n; i++)
        {
            scanf("%I64d",&a[i]);
            dp[i][1] = 1;
        }
        for (int i = 2;i <= n; i++)
        {
            for (int j = 2;j <= m; j++)
            {
                for (int k = 1;k < i; k++)
                {
                    if (a[k] < a[i]) //前i个数长度为j的递增子序列数目
                                     //=（a[i] > a[k]&&k < i）前k个数中长度为j-1的递增子序列数目的和
                        dp[i][j]+=dp[k][j-1];
                }
            }
        }
        __int64 ans = 0;
        for (int i = 1;i <= n; i++)
           ans+=dp[i][m];
        printf("%I64d
",ans);
    }
    return 0;
}