题意是求哈密顿回路的多少，可以用《基于连通性状态压缩的动态规划问题》来解，但由于只有4行，所以可以发现一些规律，
其他人写的比较多了，就不列举出来，
设f[i] 表示前i列中，第i列的第一个格子到第二个格子的哈密顿路的条数。本题的答案自然就是f[n]。
设g[i]表示前i列中，第i列的第一个格子到第四个格子的哈密顿路的条数。
f[i]的递推关系： f[i] = f[i-1] + g[i-1]
g[i]的递推关系：g[i] = f[i-1]*2+g[i-1]+g[i-2]-g[i-3]；
证明可以参考：
http://www.docin.com/p-94253938.html其中，f[1]=0, f[2]=1, f[3]=2, f[4]=6；g[1]=1, g[2]=1, g[3]=4, g[4]=8。
另外用上高精度计算。
/**//*
ID: lorelei3
TASK: vans
LANG: C++
*/
#include <fstream>
#include <memory.h>
using namespace std;
const int MAXN = 1005;
const int MAXP = 1000;
ifstream fin("vans.in");
ofstream fout("vans.out");
int n;
template<int LIM,int MAX, int LIE> class hp
{
public:
//vars
int sect[MAX];
int scnt;
//constructors
hp()
{
scnt=1;
sect[0]=0;
}
//functions
void copy(const hp<LIM,MAX,LIE> &A)
{
for (int i=0;i<A.scnt;i++)
sect[i]=A.sect[i];
scnt=A.scnt;
}
void copy(int A)
{
scnt=0;
while (A)
{
sect[scnt++]=A % LIM;
A /=LIM;
}
}
void print()
{
int i,k;
fout<<sect[scnt-1];
for (i=scnt-2;i>=0;i--)
{
k=LIM/10;
while(sect[i]<k)
{
fout<<0;
k/=10;
}
if (sect[i])
fout<<sect[i];
}
fout<<endl;
}
void plus(hp<LIM,MAX,LIE> &A,int offset=0)
{
int sc=scnt > A.scnt + offset ? scnt : A.scnt + offset;
int i,j,up=0;
for (i=0;i<sc;i++)
{
j=i - offset;
if (j<0) continue;
if (i>=scnt) sect[i]=0;
if (j>=A.scnt) A.sect[j]=0;
sect[i]+=A.sect[j] + up;
up=sect[i] / LIM;
sect[i]%=LIM;
}
scnt=sc;
if (up) sect[scnt++]=up;
}
void minus(hp<LIM,MAX,LIE> &A)
{
int sc=scnt;
int i,lend=0;
for (i=0;i<sc;i++)
{
if (i>=A.scnt) A.sect[i]=0;
sect[i]-=A.sect[i] + lend;
lend=0;
if (sect[i]<0)
{
lend=1;
sect[i]+=LIM;
}
}
scnt=sc;
if (lend) scnt--;
for (;scnt>1 && sect[scnt-1]==0;scnt--);
}
void multiply(int p)
{
if (p==0)
{
scnt=1;
sect[0]=0;
return;
}
int sc=scnt;
int i,up=0;
for (i=0;i<sc;i++)
{
if (i>=scnt) sect[i]=0;
sect[i]=sect[i] * p + up;
up=sect[i] / LIM;
sect[i]%=LIM;
}
scnt=sc;
if (up) sect[scnt++]=up;
}
hp<LIM,MAX,LIE> operator +(hp<LIM,MAX,LIE> &A)
{
hp<LIM,MAX,LIE> C(*this);
C.plus(A);
return C;
}
hp<LIM,MAX,LIE> operator -(hp<LIM,MAX,LIE> &A)
{
hp<LIM,MAX,LIE> C(*this);
C.minus(A);
return C;
}
hp<LIM,MAX,LIE> operator *(int A)
{
hp<LIM,MAX,LIE> C(*this);
C.multiply(A);
return C;
}
};
typedef hp<10000, 1000, 5> hpnum;
hpnum f[MAXN], g[MAXN];
int main(){
g[0].sect[0]=0, g[1].sect[0]=1, g[2].sect[0]=1, g[3].sect[0]=4, g[4].sect[0]=8;
f[0].sect[0]=0, f[1].sect[0]=0, f[2].sect[0]=1, f[3].sect[0]=2, f[4].sect[0]=6;
fin>>n;
if(n<=4){
fout<<f[n].sect[0]*2<<endl;
return 0;
}
for(int i=5; i<=n; ++i){
g[i-1]=f[i-2]*2+g[i-2]+g[i-3]-g[i-4];
f[i]=f[i-1]+g[i-1];
}
f[n].multiply(2);
f[n].print();
return 0;
}
posted on 2011-02-18 11:58
小阮 阅读(808)
评论(0) 编辑 收藏 引用 所属分类:
USACO