Posted on 2012-03-05 13:49
C小加 阅读(1288)
评论(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;
}