Blog·Tanky WooABOUTRSS

百练OJ 1664 放苹果

19 May 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

//ID:百练OJ 1664 放苹果 //地址:http://www.cppleyuan.com/ //个人主页:www.wutianqi.com //豆瓣小组:http://www.douban.com/group/cppleyuan/

 #include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

int nCases;
int M, N;

int dp(int m, int n)
{
    if(m == 0 || n == 1)
        return 1;
    if(m < n)   //这个地方是m < n ,而不是 m <= n,先开始画蛇添足加了“=”,结果没输出结果。
        //才发现,如果加了“=”,则适中递归退不出来。
        return dp(m, m);
    else
        return dp(m-n, n) + dp(m, n-1);
}

int main()
{
    scanf("%d", &nCases;);
    while(nCases--)
    {
        scanf("%d %d", &M;, &N;);
        printf("%d\n", dp(M, N));
    }
    return 0;
} 

//也算是一道经典的DP把,刚开始做DP题这道题目倒是不错! //不是很难,可以理解DP的简便。