P1139 单向双轨道

admin

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

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.     {
    
52. 
    
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

楼上YTC做得很好，大家就是要这样做题，。话说，这个题，我还么有AC呢。

七夜劫年

#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;
}