hiho 1251 Today Isa Rainy Day(欲張り状態圧縮bfs)

hiho 1251タイトルリンク(C題)
テーマの大意
2つとも1から与えられます.6からなる長さが等しい文字列で、毎回2つの操作を行うことができます.操作1は、数字のような数字をすべて別の数字に変更することである.操作2は、ある位置の数字を別の数字に変更する(変更する).2つの動作の代価は同じであり、与えられた2番目の列が1番目の列になるために必要な最小限の代価を求める.
に答える
この問題は知的障害があり、検索剪断や記憶化はこの問題(剪断と記憶化は同時に使用できないが、論理的には間違っている)を通過できると勘違いしている.実はよく考えてみると、各層の分岐が多すぎると必ず爆発し、記憶化状態が多すぎて耐えられないので、この考え方は最初から間違っていることに気づくはずです.
この問題はまず、操作1と操作2が別々に行われていることを考え、まず操作1を終えてから操作2をしなければならない.この結論は実は最初から推測していたが、証明しにくいと思って続けなかった.後で大体証明して発見するのは難しくない.
i番目の位置が1であると仮定すると、まず実行操作2が2になり、操作1が実行され、1に戻ると明らかに最初のステップが余計になる.3になると,まず操作1を実行してすべての2を3(i位置の1を含まない)にし,次に操作2を実行して直接i番目の位置の1を3にするという代価となる.このことから,操作1を先に実行し,操作2を実行することで,最小限の代価を保証できる.
したがって、操作1が変化したすべての状態を列挙し、操作2を実行することができる.操作1の状態をどのように列挙して最小の代価を求めるのか.私の最初の考えは配列してやることですが、複雑な感じがします.その後、ネット上の問題解を見て、bfsを使うことを思い出した.6次元配列p[a][b][c][d][e][f]で1を表すことができる.6はそれぞれ操作1を経て対応する数字に必要な最小ステップ数(種類を見るだけで、個数を見る必要はない)となり、ステップ毎の遷移が1であるため、bfsで前処理することができる.6次元配列は6進数で表すことができます.
比較的簡単なやり方で、非常に強いです.前処理の時間的複雑度はO(68),空間的複雑度はO(66)であった.列挙状態計算の複雑さはO(6^6*len)である.

#include 
#include 
#include 
#include 
#include 
using namespace std;

#define For(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
#define Mem(a,b) memset(a,b,sizeof(a))

const int maxn=110+10;
const int maxL=6*6*6*6*6*6+100;
char s1[maxn],s2[maxn];
int N;
int o[maxL],F[maxL];

void change(int *p,int &x,int d)    //          
{
    if (d)
    {
        x=0;
        for (int i=0,ss=1; i<6; i++)
        {
            x+=ss*p[i];
            ss*=6;
        }
    }
    else
    {
        for (int i=0,ss=x; i<6; i++)
        {
            p[i]=ss%6;
            ss/=6;
        }
    }
}

void extend(int x,int *p,int u,int v,int &t)   //   
{
    static int q[8];
    bool flag=0;
    for (int i=0; i<6; i++)
        if (p[i]==u)
        {
            flag=1;
            q[i]=v;
        }
        else q[i]=p[i];
    if (!flag) return ;
    int y;
    change(q,y,1);
    if (F[y]==-1) o[++t]=y,F[y]=F[x]+1;
}

void Prepare()          // bfs   
{
    static int p[8];
    Mem(F,255);
    int h=0,t=0;
    int s=0+6+2*6*6+3*6*6*6+4*6*6*6*6+5*6*6*6*6*6;  //     
    o[h]=s; F[s]=0;
    for (; h<=t; h++)
    {
        int x=o[h];
        change(p,x,0);
        for (int i=0; i<6; i++)
            for (int j=0; j<6; j++)
                if (i!=j) extend(x,p,i,j,t);   //   
    }
}

int Done(char *s1,char *s2,int state)       //     ，     
{
    static int p[8];
    change(p,state,0);
    int ret=F[state];
    For(i,1,N)
    {
        int u=s2[i]-'0'-1;
        int v=s1[i]-'0'-1;
        ret+=(p[u]!=v);
    }
    return ret;
}

int main(int argc, char* argv[])
{
    Prepare();
    for (; scanf("%s%s",s1+1,s2+1)!=EOF; )
    {
        N=strlen(s1+1);
        int ans=N;
        For(i,0,maxL-1)
            if (F[i]!=-1) ans=min(ans,Done(s1,s2,i));
        printf("%d
",ans);
    }
    return 0;
}