随笔-141  评论-9  文章-3  trackbacks-0
题意是求哈密顿回路的多少,可以用《基于连通性状态压缩的动态规划问题》来解,但由于只有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
++]=% 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
=- offset;
                
if (j<0continue;
                
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
<1000010005> 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 小阮 阅读(825) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理