题意是求哈密顿回路的多少,可以用《基于连通性状态压缩的动态规划问题》来解,但由于只有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。
另外用上高精度计算。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: vans
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
#include <memory.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAXN = 1005;
const int MAXP = 1000;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
ifstream fin("vans.in");
ofstream fout("vans.out");
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
template<int LIM,int MAX, int LIE> class hp
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
public:
//vars
int sect[MAX];
int scnt;
//constructors
hp()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scnt=1;
sect[0]=0;
}
//functions
void copy(const hp<LIM,MAX,LIE> &A)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for (int i=0;i<A.scnt;i++)
sect[i]=A.sect[i];
scnt=A.scnt;
}
void copy(int A)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scnt=0;
while (A)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
sect[scnt++]=A % LIM;
A /=LIM;
}
}
void print()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int i,k;
fout<<sect[scnt-1];
for (i=scnt-2;i>=0;i--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
k=LIM/10;
while(sect[i]<k)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
fout<<0;
k/=10;
}
if (sect[i])
fout<<sect[i];
}
fout<<endl;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
void plus(hp<LIM,MAX,LIE> &A,int offset=0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int sc=scnt > A.scnt + offset ? scnt : A.scnt + offset;
int i,j,up=0;
for (i=0;i<sc;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int sc=scnt;
int i,lend=0;
for (i=0;i<sc;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if (i>=A.scnt) A.sect[i]=0;
sect[i]-=A.sect[i] + lend;
lend=0;
if (sect[i]<0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
lend=1;
sect[i]+=LIM;
}
}
scnt=sc;
if (lend) scnt--;
for (;scnt>1 && sect[scnt-1]==0;scnt--);
}
void multiply(int p)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if (p==0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scnt=1;
sect[0]=0;
return;
}
int sc=scnt;
int i,up=0;
for (i=0;i<sc;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
hp<LIM,MAX,LIE> C(*this);
C.plus(A);
return C;
}
hp<LIM,MAX,LIE> operator -(hp<LIM,MAX,LIE> &A)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
hp<LIM,MAX,LIE> C(*this);
C.minus(A);
return C;
}
hp<LIM,MAX,LIE> operator *(int A)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
hp<LIM,MAX,LIE> C(*this);
C.multiply(A);
return C;
}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef hp<10000, 1000, 5> hpnum;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
hpnum f[MAXN], g[MAXN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
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;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin>>n;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(n<=4)
{
fout<<f[n].sect[0]*2<<endl;
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=5; i<=n; ++i)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
g[i-1]=f[i-2]*2+g[i-2]+g[i-3]-g[i-4];
f[i]=f[i-1]+g[i-1];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
f[n].multiply(2);
f[n].print();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted on 2011-02-18 11:58
小阮 阅读(820)
评论(0) 编辑 收藏 引用 所属分类:
USACO