连环锁

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 1260		Accepted: 403

Description

许多人一定很熟悉九连环（如下图），九个环被串在一起，操作规则如下：第一个（右边）环可以任意装卸，如果第k个环没有被卸掉，而第k个环前边（右边）的所有环都被卸掉，则第k+1个环（第k个环左边的环）可以任意装卸（如果存在的话）。
用0表示此换被卸掉，1表示此环没有被卸掉，则九连环的每个状态可以用一个长度为9的二进制串来表示，如：111111001经过一次操作可以变成111111000，也可以变成111111011，111111111经过一次操作可以变成111111110，也可以变成111111101。
【Poj 1832】连环锁-LMLPHP

任务描述：
你现在要操作的是一个n连环，n为正整数，给出n连环的两种状态，计算出从第一种状态变换到第二种状态所需要的最少步数。

Input

第一行是一个正整数m，表示有m组测试数据。
每组测试数据一共3行，第一行是一个正整数n (0 < n < 128)，后两行每一行描述一种状态，n个数（0或1），用空格隔开。

Output

对于每一组测试数据输出一行，一个非负整数，表示从第一种状态变换到第二种状态所需要的最少步数。

Sample Input

Sample Output

7

11

Source

qinlu@POJ

Position

http://poj.org/problem?id=1832

Solution

【Poj1090】Chain

看下这道题基本就会做了,一个状态到另一个状态=(一个状态→ 0)-(一个状态→0),加些高精度减法,与比大小即可

Code

// This file is made by YJinpeng，created by XuYike's black technology automatically.

// Copyright (C) 2016 ChangJun High School, Inc.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#define MOD 1000000007

#define INF 1e9

using namespace std;

typedef long long LL;

const int MAXN=;

inline int max(int &x,int &y) {return x>y?x:y;}

inline int min(int &x,int &y) {return x<y?x:y;}

inline int gi() {

    register int w=,q=;register char ch=getchar();

    while((ch<''||ch>'')&&ch!='-')ch=getchar();

    if(ch=='-')q=,ch=getchar();

    while(ch>=''&&ch<='')w=w*+ch-'',ch=getchar();

    return q?-w:w;

}

const int __bmod__=;

struct BN{

    int a[];

    BN(){memset(a,,sizeof(a));}

    int& operator [](int n){return a[n];}

    void get(int n){

         memset(a,,sizeof(a));

         a[]=n;if(a[])a[]=;

         while(a[a[]+]){a[a[]+]=a[a[]]/__bmod__;a[a[]++]%=__bmod__;}

    }

    bool operator <(BN b) const{

        if(a[]<b[])return ;

        if(a[]>b[])return ;

        for(int i=a[];i>=;i--){

            if(a[i]>b[i])return ;

            if(a[i]<b[i])return ;

        }

        return ;

    }

    BN operator -(BN b) const{

        BN ans=*this;int q=;

        if(ans<b)swap(ans,b),q=-;

        for(int i=;i<=ans[];i++){

            ans[i]=ans[i]-b[i];

            if(ans[i]<){ans[i+]--;ans[i]+=__bmod__;}

        }

        while(ans[]&&!ans[ans[]])ans[]--;

        for(int i=;i<=ans[];i++)ans[i]*=q;

        return ans;

    }

    BN operator +(BN b) const{

        b[]=max(a[],b[]);

        for(int i=;i<=b[];i++){

            b[i]+=a[i];

            if(b[i]>=__bmod__){b[i+]+=b[i]/__bmod__;b[i]%=__bmod__;}

        }

        if(b[b[]+])b[]++;

        return b;

    }

    BN operator *(BN b) const{

        BN ans;

        ans[]=a[]+b[]-;

        for(int i=;i<=a[];i++)

            for(int o=;o<=b[];o++){

                int now=i+o-;

                ans[now]+=a[i]*b[o];

            }

        for(int i=;i<=ans[];i++)if(ans[i]>=__bmod__){ans[i+]+=ans[i]/__bmod__;ans[i]%=__bmod__;}

        if(ans[ans[]+])ans[]++;

        return ans;

    }

    void print(){printf("%d",a[a[]]);for(int i=a[]-;i>=;i--)printf("%.5d",a[i]);printf("\n");}

}now,f[],o,t,up,mu;

int a[MAXN];

int main()

{

    freopen("1832.in","r",stdin);

    freopen("1832.out","w",stdout);

    int T=gi();

    while(T--){

        int n=gi();

        for(int x=;x<;x++){

            for(int i=n;i>=;i--)a[i]=gi();

            f[x].get(a[]),o.get(-a[]),t.get(),up.get(),mu.get();

            for(int i=;i<=n;i++){

                if(a[i])

                    now=f[x],f[x]=o+t+up,o=now;

                else o=o+t+up;

                t=t*mu+up;

            }

        }

        if(f[]<f[])

            (f[]-f[]).print();

        else (f[]-f[]).print();

    }

    return ;

}