当前位置:编程学习 > C/C++ >>

HDU 1267——下沙的沙子有几粒?

相当水的DP,状态方程也很简单:dp(m,n)=dp(m,n-1)+dp(m-1,n),其中m<n的话排列的情况不存在。
dp的精髓就是状态方程。
[cpp] 
#include <iostream>  
#include <cstring>  
using namespace std;  
  
__int64 dp[21][21];  
  
int main()  
{  
    int m,n;  
    while(cin>>m>>n)  
    {  
        memset(dp,0,sizeof(dp));  
        if(m<n)  
        {  
            cout<<0<<endl;  
            continue;  
        }  
        else  
        {     
            for(int a=1;a<=m;a++)  
            {  
                dp[a][0]=1;  
            }  
            for(int i=1;i<=20;i++)  
            {  
                for(int j=1;j<=i;j++)  
                {  
                    dp[i][j]=dp[i][j-1]+dp[i-1][j];  
                }  
            }  
          
            cout<<dp[m][n]<<endl;  
        }  
          
    }  
      
      
      
    return 0;  
}   
 
补充:软件开发 , C++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,