sijing

HDOJ 1267下沙的沙子有几粒? (DP)

如果用f [ i ] [ j ]代表有i个H和j个D的序列的种数,则:
f [ i ][ j ] = f [ i-1 ][ j ] + f [ i ][ j-1 ];
考虑最后一个字母是H还是D的情况,最后一个字母是D的情况的序列种数是f [ i ][ j-1 ],最后一个字母是H的情况的序列种数是f [ i-1 ][ j ]。
#include <iostream>
#include 
<cstdio>//包含此头文件是为了调用C风格的输出函数printf.
using namespace std;

int main()
{
    __int64 a[
21][21]={0};//也可以用memset(a,0,sizeof(a))需要包含头文件<cstring>
    
//不过我刚刚测试了一下,不包含头文件<string.h>或者<memory.h>也没有关系。不懂!
    
//甚至不初始化,该题也能AC!!!
    int i,j;
    
for(i=0;i<=20;i++)
    {
        a[i][
0]=1;//只要‘D’的个数为0,‘H’的个数为任意数,都是一种序列
        a[0][i]=0;//只要‘H’的个数为0,‘D’的个数为任意数,这种序列都不满足
    }
    
for(i=1;i<=20;i++)
        
for(j=1;j<=20;j++)
        {
            
if(i<j)          //遇到‘H’个数少于‘D’个数时,这种序列不满足。
                a[i][j]=0;
            
else             //‘H’个数大于或者等于‘D’个数时,进入状态转移方程
                a[i][j]=a[i-1][j]+a[i][j-1];///DP核心
        }
    
int m,n;
    
while(cin>>m>>n)
    {
        printf(
"%I64d\n",a[m][n]);
    }
    
return 0;
}

posted on 2010-08-02 10:24 宇骐 阅读(684) 评论(2)  编辑 收藏 引用

评论

# re: HDOJ 1267下沙的沙子有几粒? (DP) 2010-08-07 23:11 Geek.tan

不包含#include <cstdio> ,也可以使用scanf 和 printf,只要有#include<iostream>  回复  更多评论   

# re: HDOJ 1267下沙的沙子有几粒? (DP) 2011-01-21 20:57 H

@Geek.tan
可能是VC兼容性比较好吧!在VC里用C++好像不怎么区分出C来。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年4月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜