递推

作者: Tsukinousag | 来源:发表于2021-01-24 20:08 被阅读0次

    3.1费解的开关

    原题链接

    #include<iostream>
    #include<cstring>
    
    using namespace std;
    const int INF=1e6+10;
    
    char g[10][10];
    
    void turn(int x,int y)
    {
        int dx[5]={0,-1,0,1,0},dy[5]={0,0,1,0,-1};
        for(int i=0;i<5;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a>=0&&a<5&&b>=0&&b<5)
                g[a][b]^=1;
        }
    }
    
    int work()
    {
        int ans=INF;
        //枚举状态
        for(int k=0;k<1<<5;k++)//第一行摁或者不摁,有32种可能数来求最优解,00000~11111
        {
            int res=0;
            char backup[10][10];
            memcpy(backup,g,sizeof g);
            ///////////////////枚举第一行的摁操作,那首先规定从前往后看第一行的第j位是否是1,如果是,就要turn一下
            //////////////////例如00000,表示5展灯都不摁,11111,表示5展灯都摁,所以我们就把第一行的所有摁的状态都枚举一遍
            for(int j=0;j<5;j++)
                if(k>>j&1)
                {
                    res++;
                    turn(0,j);
                }
            //////////////////枚举前四行的状态
            for(int j=0;j<4;j++)
            {
                for(int i=0;i<5;i++)
                {
                    if(g[j][i]=='0')
                    {
                        res++;
                        turn(j+1,i);
                    }
                }
            }
            //////////////////判断最后一行是不是全是1即可
            bool is_successful=true;
            for(int j=0;j<5;j++)
            {
                if(g[4][j]=='0')
                {
                    is_successful=false;
                    break;
                }
            }
    
            if(is_successful)    ans=min(ans,res);
    
            memcpy(g,backup,sizeof g);//g数组恢复原状重新枚举下一个状态
        }
        if(ans>6)   ans=-1;
    
        return ans;
    }
    
    
    int main()
    {
        int n;
        cin>>n;
        while(n--)
        {
            for(int i=0;i<5;i++)
                cin>>g[i];
            cout<<work()<<endl;
        }
        return 0;
    }
    

    3.2 奇怪的汉诺塔

    原题链接

    #include<iostream>
    #include<cstring>
    
    using namespace std;
    
    int d[15],f[15];
    
    int main()
    {
        d[1]=1;
        for(int i=2;i<=12;i++)
            d[i]=2*d[i-1]+1;
            
        memset(f,0x3f,sizeof f);
        
        f[1]=1;
        for(int i=2;i<=12;i++)//i个盘子4塔问题
        {
            //枚举前j个盘子(j<i)先移动
            for(int j=1;j<i;j++)
            {
                f[i]=min(f[i],f[j]*2+d[i-j]);
            }
        }
        for(int i=1;i<=12;i++) cout<<f[i]<<endl;
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:递推

          本文链接:https://www.haomeiwen.com/subject/qmpmzktx.html