首页 > 其他 > 详细

hdu1267(递推)

时间:2014-12-07 19:04:36      阅读:253      评论:0      收藏:0      [点我收藏+]

 

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1267

题意:
假定一个字符串由m个H和n个D组成,从左到右扫描该串,如果字符H的累计数
总是不小于字符D的累计数,那么,满足条件的字符串总数。

状态转移方程:dp[i+1][j]+=dp[i][j]//在后面加一个H

                    dp[i][j+1]+=d[i][j]//在后面加一个D

bubuko.com,布布扣
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define N 10010
using namespace std;
LL dp[50][50];
void init()
{
    dp[0][0]=1;
    for(int i=0;i<=20;i++)
    for(int j=0;j<=i;j++)
    {
        dp[i+1][j]+=dp[i][j];
        if(i>j)dp[i][j+1]+=dp[i][j];
    }
}
int main()
{
    init();
    int n,m;
    while(scanf("%d%d",&n,&m)>0)
    {
        printf("%I64d\n",dp[n][m]);
    }
}
View Code

 

hdu1267(递推)

原文:http://www.cnblogs.com/lienus/p/4149622.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!