Posted on 2012-03-05 13:49
C小加 閱讀(1338)
評論(3) 編輯 收藏 引用 所屬分類:
解題報告
DP或卡特蘭數(shù)。
弱爆了。做題的時候只想著用一個狀態(tài)去做，結(jié)果悲劇了。后來成哥提醒用二維的，我才發(fā)現(xiàn)得用兩個狀態(tài)去寫。哎，怎么沒想到兩個狀態(tài)呢。
題意：在一個瓶子里有N片藥，每次吃半片，從瓶子里可能拿出整片，也可能拿出半片，如果拿出整片，記為W，半片記為H。問有多少種排列。
第一個狀態(tài)：完整藥片的數(shù)量。第二個狀態(tài)：半片藥片的數(shù)量。
F（i，j）=f（i-1,j+1）+f（I，j-1）；
當吃的是整片時，i-1，半片的增加一個，j+1。
當吃的是半片時，i不變，j-1。
用兩個狀態(tài)寫的時候這個題就很水了。不過提交的時候在g++下用lang lang WA，改成int64在C++下提交就AC了。很是不解。
卡特蘭數(shù)的方法就不多說了。。。。你懂的。。
#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;
}