【组合数学】Critical Mass, UVa580

刘汝佳书上分析得很好。我就不多写了。

#include<bits/stdc++.h>
using namespace std;
int n;typedef long long LL;
LL f[40],g[40],w[40];
int main()
{
	ios::sync_with_stdio(false);
	f[0] = f[1] = f[2] = 0;
	g[0] = 1;g[1] = 2;g[2] = 4;w[0] = 1;
	for(int i=1;i<=30;i++)
		w[i]=w[i-1]*2;
	for(int i=3;i<=30;i++)
	{
		f[i] = w[i-3];
		for(int j=2;j<=i-2;j++)
			f[i]+=g[j-2]*w[i-j-2];
		g[i] = w[i]-f[i];
	}
	while(cin>>n)
	{
		if(!n)break;
		cout<<f[n]<<endl;
	}
	return 0;
}