华师一附中OI组

标题: P1139 单向双轨道 [打印本页]
作者: admin    时间: 2018-5-12 23:07
标题: P1139 单向双轨道
https://www.luogu.org/problemnew/show/P1139
题目描述
如图所示l，某火车站有B，C两个调度站，左边入口A处有n辆火车等待进站(从左到右以a、b、c、d编号)，右边是出口D，规定在这一段，火车从A进入经过B、C只能从左向右单向开，并且B、C调度站不限定所能停放的车辆数。



从文件输入n及n个小写字母的一个排列，该排列表示火车在出口D处形成的从左到右的火车编号序列。输出为一系列操作过程，每一行形如“h L R”的字母序列，其中h为火车编号，L为h车原先所在位置(位置都以A、B、C、D表示)，R为新位置。或者输出‘NO’表示不能完成这样的调度。

输入输出格式
输入格式：
一个数n(1<n<27)及由n个小写字母组成的字符串。

输出格式：
可以调度则输出最短的调度序列，当有多种方案时输出按操作（L、R）字典序最小的方案，不可以调度时则输出‘NO’。

输入输出样例
输入样例#1：
3
cba
输出样例#1：
c A B
b A B
a A D
b B D
c B D
作者: YTC    时间: 2018-7-6 19:53
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. using namespace std;
  5. int n;
  6. int a[30],b[30],c[30],d[30];//4个栈
  7. int maxd;
  8. int to[30];
  9. char s[30];
  10. int f[30][3];//步
  11. int ta,tb,tc,td;//栈顶编号
  12. void dfs(int x)
  13. {
  14.     if(x+n-1-td>maxd) return;
  15.     if(d[td]!=to[td]) return;//把td写成X，结果调不出来
  16.     if(x==maxd+1&&!ta&&!tb&&!tc)
  17.     {
  18.       //  cout<<maxd<<endl;
  19.         for(int i=1;i<=maxd;i++)
  20.             printf("%c %c %c\n",f[i][0]+'a'-1,f[i][1]+'A'-1,f[i][2]+'A'-1);
  21.         exit(0);
  22.     }
  23.     if(x>=maxd+1) return;
  24.     int tmp;//中间变量，避免出错
  25.     if(ta)
  26.     {
  27.         tmp=a[ta]; f[x][0]=tmp;f[x][1]=1;f[x][2]=2;ta--;tb++;b[tb]=tmp; dfs(x+1);
  28.         ta++;tb--;a[ta]=tmp;
  29.     }
  30.     if(ta)
  31.     {
  32.         tmp=a[ta];f[x][0]=tmp;f[x][1]=1;f[x][2]=3;ta--;tc++;c[tc]=tmp; dfs(x+1);
  33.         ta++;tc--;a[ta]=tmp;
  34.     }
  35.     if(ta)
  36.     {
  37.         tmp=a[ta];f[x][0]=tmp;f[x][1]=1;f[x][2]=4;ta--;td++;d[td]=tmp; dfs(x+1);
  38.         ta++;td--;a[ta]=tmp;
  39.     }
  40.     if(tb)
  41.     {
  42.         tmp=b[tb];f[x][0]=tmp;f[x][1]=2;f[x][2]=3;tb--;tc++;c[tc]=tmp; dfs(x+1);
  43.         tb++;tc--;b[tb]=tmp;
  44.     }
  45.     if(tb)
  46.     {
  47.         tmp=b[tb];f[x][0]=tmp;f[x][1]=2;f[x][2]=4;tb--;td++;d[td]=tmp; dfs(x+1);
  48.         tb++;td--;b[tb]=tmp;
  49.     }
  50.     if(tc)
  51.     {

  53.         tmp=c[tc];f[x][0]=tmp;f[x][1]=3;f[x][2]=4;tc--;td++;d[td]=tmp; dfs(x+1);
  54.         tc++;td--;c[tc]=tmp;
  55.     }
  56. }
  57. int main()
  58. {
  59.     cin>>n;
  60.     for(int i=1;i<=n;i++) cin>>s[i];
  61.    // for(int i=1;i<=n;i++) swap(s[i],s[n-i+1]);// 这里用swap不知为何交换不了
  62.     //for(int i=1;i<=n;i++) cout<<s[i];
  63.     for(int i=1;i<=n;i++) a[i]=i;
  64.     ta=n;
  65.     for(int i=1;i<=n;i++) to[i]=s[n-i+1]-'a'+1;
  66.    //for(int i=1;i<=3;i++) cout<<a[i];
  67.     //for(int i=1;i<=3;i++) cout<<to[i];
  68.     for(maxd=0;maxd<=3*n;maxd++) dfs(1);
  69.     cout<<"NO";
  70.     return 0;
  71. }
复制代码

迭代加深
作者: admin    时间: 2018-7-6 22:02
楼上YTC做得很好，大家就是要这样做题，。话说，这个题，我还么有AC呢。
作者: 七夜劫年    时间: 2018-11-4 16:15
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
char s[27];
char a[110],b[110],c[110],d[110];
char s1[30010],ss[30010];
int la,lb,lc,ll;
int lr=1;
int minl=2147483647;

inline void add(char a,char b,char c)
{
    ss[ll++]=a;
    ss[ll++]=' ';
    ss[ll++]=b;
    ss[ll++]=' ';
    ss[ll++]=c;
    ss[ll++]='\n';
}

void dfs()
{
    if( ll > minl ) return;

    if( lr == n+1 )
    {
        ss[ll]=0;
        if( ll < minl || ll == minl  && strcmp(ss,s1) == -1 )
        {
            minl=ll;
            strcpy(s1,ss);
        }
        return;
    }
    char xx;

    if( la )
    {
        xx=a[la-1];
        la--;

        if( xx == d[n-lr] )
        {
            lr++;
            add(xx,'A','D');
            dfs();
            lr--;
            ll-=6;
        }
        else
        {
            b[lb++]=xx;
            add(xx,'A','B');
            dfs();
            lb--;
            ll-=6;

            c[lc++]=xx;
            add(xx,'A','C');
            dfs();
            lc--;
            ll-=6;
        }
        a[la++]=xx;
    }

    if( lb )
    {
        xx=b[lb-1];
        lb--;

        if( xx == d[n-lr] )
        {
            lr++;
            add(xx,'B','D');
            dfs();
            lr--;
            ll-=6;
        }
        else
        {
            c[lc++]=xx;
            add(xx,'B','C');
            dfs();
            lc--;
            ll-=6;
        }
        b[lb++]=xx;
    }

    if( lc )
    {
        xx=c[lc-1];

        if( xx == d[n-lr] )
        {
            lr++;
            lc--;
            add(xx,'C','D');
            dfs();
            c[lc++]=xx;
            lr--;
            ll-=6;
        }
    }


}

int main()
{
    scanf("%d%s",&n,s);

    for(int i=0;i<n;i++)
    {
        a[i]=i+'a';
        d[i]=s[i];
    }
    la=n;

    dfs();

    printf("%s",s1[0]?s1:"NO");
    return 0;
}



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2