首页 > ACM题库 > HDU-杭电 > HDU 1799 循环多少次?-动态规划-[解题报告] C++
2013
12-23

HDU 1799 循环多少次?-动态规划-[解题报告] C++

循环多少次?

问题描述 :

  我们知道,在编程中,我们时常需要考虑到时间复杂度,特别是对于循环的部分。例如,
如果代码中出现
for(i=1;i<=n;i++) OP ;
那么做了n次OP运算,如果代码中出现
fori=1;i<=n; i++)
  for(j=i+1;j<=n; j++) OP;
那么做了n*(n-1)/2 次OP 操作。
现在给你已知有m层for循环操作,且每次for中变量的起始值是上一个变量的起始值+1(第一个变量的起始值是1),终止值都是一个输入的n,问最后OP有总共多少计算量。

输入:

  有T组case,T<=10000。每个case有两个整数m和n,0<m<=2000,0<n<=2000.

输出:

  对于每个case,输出一个值,表示总的计算量,也许这个数字很大,那么你只需要输出除1007留下的余数即可。

样例输入:

2
1 3
2 3

样例输出:

3
3

2011-12-30 17:35:04

地址:http://acm.hdu.edu.cn/showproblem.php?pid=1799

题意:中文。

mark:其实就是组合数。。。因为m重循环就是在n个数字里选n个作为变量。。。

代码:

# include <stdio.h>

int dp[2010][2010] ;


void init()
{
    int i, j ;
    dp[0][0] = 1 ;
    for (i = 1 ; i <= 2000 ; i++)
    {
        dp[i][0] = 1 ;
        for (j = 1 ; j <= i ; j++)
            dp[i][j] = (dp[i-1][j] + dp[i-1][j-1]) % 1007 ;
    }
}


int main ()
{
    int T, n, m ;
    init() ;
    scanf ("%d", &T) ;
    while (T--)
    {
        scanf ("%d%d", &m, &n) ;
        printf ("%d\n", dp[n][m]) ;
    }
    return 0 ;
}

解题报告转自:http://www.cnblogs.com/lzsz1212/archive/2012/01/07/2315416.html