Posted on 2012-03-05 13:49
C小加 阅读(1302)
评论(3) 编辑 收藏 引用 所属分类:
解题报告
DP或卡特兰数。
弱爆了。做题的时候只想着用一个状态去做,结果悲剧了。后来成哥提醒用二维的,我才发现得用两个状态去写。哎,怎么没想到两个状态呢。
题意:在一个瓶子里有N片药,每次吃半片,从瓶子里可能拿出整片,也可能拿出半片,如果拿出整片,记为W,半片记为H。问有多少种排列。
第一个状态:完整药片的数量。第二个状态:半片药片的数量。
F(i,j)=f(i-1,j+1)+f(I,j-1);
当吃的是整片时,i-1,半片的增加一个,j+1。
当吃的是半片时,i不变,j-1。
用两个状态写的时候这个题就很水了。不过提交的时候在g++下用lang lang WA,改成int64在C++下提交就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;
}