C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

hdu 4165 Pills 解题报告

Posted on 2012-03-05 13:49 C小加 阅读(1302) 评论(3)  编辑 收藏 引用 所属分类: 解题报告

DP或卡特兰数

弱爆了。做题的时候只想着用一个状态去做,结果悲剧了。后来成哥提醒用二维的,我才发现得用两个状态去写。哎,怎么没想到两个状态呢。
题意:在一个瓶子里有N片药,每次吃半片,从瓶子里可能拿出整片,也可能拿出半片,如果拿出整片,记为W,半片记为H。问有多少种排列。

第一个状态:完整药片的数量。第二个状态:半片药片的数量。

Fij=fi-1,j+1+fIj-1);

当吃的是整片时,i-1,半片的增加一个,j+1

当吃的是半片时,i不变,j-1

用两个状态写的时候这个题就很水了。不过提交的时候在g++下用lang lang WA,改成int64C++下提交就AC了。很是不解。

卡特兰数的方法就不多说了。。。。你懂的。。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
__int64 f[33][33];

int main()
{
    memset(f,0,sizeof(f));
    int k=30;
    for(int i=0;i<k;i++) f[1][i]=i+1;
    for(int i=2;i<=30;i++)
    {
        k--;
        f[i][0]=f[i-1][1];
        for(int j=1;j<k;j++)
        {
            f[i][j]=f[i][j-1]+f[i-1][j+1];
        }
    }


   int s;
   while(scanf("%d",&s),s)
   {
       printf("%I64d\n",f[s][0]);
   }
    return 0;
}

 

Feedback

# re: hdu 4165 Pills 解题报告  回复  更多评论   

2012-03-05 18:05 by 张久杰
dp[][] 代表的具体意义说下好吗??

# re: hdu 4165 Pills 解题报告  回复  更多评论   

2012-03-05 18:07 by C小加
dp[i][j]=剩下i片整药和j片半药时的序列数@张久杰

# re: hdu 4165 Pills 解题报告  回复  更多评论   

2012-03-05 19:53 by 远行
前几天做了这个题,不过我用的是记忆化搜索,dp习惯这样写了

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