SGU 237 갤 럭 시 X:에피소드 I-마 인 드 마스터 스

제목 링크:http://acm.sgu.ru/problem.php?contest=0&problem=237
제목:꼬치 를 드 립 니 다.별 번 호 는 임의로 바 꿀 수 있 습 니 다(빈 문자열 포함).물음 표 는 한 글자 로 만 바 꿀 수 있 고 느낌표 는 세 글자 로 만 바 꿀 수 있 습 니 다.교체 후의 가장 짧 은 답장 문자열 을 구 합 니까?가장 짧 은 경우 사전 순서 가 가장 작 습 니까?
사고방식:f[i][j]는 i 에서 j 까지 회 문 열 을 형성 하 는 것 이 가장 작다 는 것 을 나타 낸다.길 이 는 작은 것 부터 큰 것 까지 매 거 하면 된다.

#include <iostream>

#include <cstdio>

#include <string.h>

#include <algorithm>

#include <cmath>

#include <vector>

#include <queue>

#include <set>

#include <stack>

#include <string>

#include <map>





#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)<(y)?(x):(y))

#define abs(x) ((x)>=0?(x):-(x))

#define i64 long long

#define u32 unsigned int

#define u64 unsigned long long

#define clr(x,y) memset(x,y,sizeof(x))

#define CLR(x) x.clear()

#define ph(x) push(x)

#define pb(x) push_back(x)

#define Len(x) x.length()

#define SZ(x) x.size()

#define PI acos(-1.0)

#define sqr(x) ((x)*(x))

#define MP(x,y) make_pair(x,y)



#define FOR0(i,x) for(i=0;i<x;i++)

#define FOR1(i,x) for(i=1;i<=x;i++)

#define FOR(i,a,b) for(i=a;i<=b;i++)

#define DOW0(i,x) for(i=x;i>=0;i--)

#define DOW1(i,x) for(i=x;i>=1;i--)

#define DOW(i,a,b) for(i=a;i>=b;i--)

using namespace std;





void RD(int &x){scanf("%d",&x);}

void RD(i64 &x){scanf("%I64d",&x);}

void RD(u32 &x){scanf("%u",&x);}

void RD(double &x){scanf("%lf",&x);}

void RD(int &x,int &y){scanf("%d%d",&x,&y);}

void RD(i64 &x,i64 &y){scanf("%I64d%I64d",&x,&y);}

void RD(u32 &x,u32 &y){scanf("%u%u",&x,&y);}

void RD(double &x,double &y){scanf("%lf%lf",&x,&y);}

void RD(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}

void RD(i64 &x,i64 &y,i64 &z){scanf("%I64d%I64d%I64d",&x,&y,&z);}

void RD(u32 &x,u32 &y,u32 &z){scanf("%u%u%u",&x,&y,&z);}

void RD(double &x,double &y,double &z){scanf("%lf%lf%lf",&x,&y,&z);}

void RD(char &x){x=getchar();}

void RD(char *s){scanf("%s",s);}

void RD(string &s){cin>>s;}





void PR(int x) {printf("%d
",x);}

void PR(i64 x) {printf("%I64d
",x);}

void PR(u32 x) {printf("%u
",x);}

void PR(u64 x) {printf("%llu
",x);}

void PR(double x) {printf("%.4lf
",x);}

void PR(char x) {printf("%c
",x);}

void PR(char *x) {printf("%s
",x);}

void PR(string x) {cout<<x<<endl;}



const int N=800;

char a[N],b[N],g[3][N][N];

int f[3][N],n;



int i,j,k,p0,p1,p2;

char c1,c2;



void assign(char *s,int L)

{

    f[p2][i]=L;

    strcpy(g[p2][i],s);

}



void update(char *s,int L)

{

    if(f[p2][i]>L||f[p2][i]==L&&strcmp(g[p2][i],s)>0)

    {

        assign(s,L);

    }

}



int main()

{

    gets(b);

    for(i=0;b[i];i++)

    {

        if(b[i]=='!') a[n++]='?',a[n++]='?',a[n++]='?';

        else a[n++]=b[i];

    }

    for(i=0;i<n;i++)

    {

        if(a[i]=='*') f[1][i]=0;

        else

        {

            f[1][i]=1;

            if(a[i]=='?') g[1][i][0]='a';

            else g[1][i][0]=a[i];

        }

    }

    p0=0;p1=1;p2=2;

    for(j=1;j<n;j++)

    {

        for(i=0;i+j<n;i++)

        {

            c1=a[i];

            c2=a[i+j];

            if(c1=='*')

            {

                if(c2=='*')

                {

                    assign(g[p0][i+1],f[p0][i+1]);

                    update(g[p1][i],f[p1][i]);

                    update(g[p1][i+1],f[p1][i+1]);

                }

                else

                {

                    assign(g[p1][i+1],f[p1][i+1]);

                    if(c2=='?') c2='a';

                    strcpy(b+1,g[p1][i]);

                    k=f[p1][i];

                    b[0]=b[k+1]=c2;

                    b[k+2]=0;

                    k+=2;

                    update(b,k);

                }

            }

            else if(c2=='*')

            {

                assign(g[p1][i],f[p1][i]);

                if(c1=='?') c1='a';

                strcpy(b+1,g[p1][i+1]);

                k=f[p1][i+1];

                b[0]=b[k+1]=c1;

                b[k+2]=0;

                k+=2;

                update(b,k);

            }

            else

            {

                if(f[p0][i+1]>=800||c1!=c2&&c1!='?'&&c2!='?')

                {

                    assign("",800);

                }

                else

                {

                    if(c1=='?')

                    {

                        if(c2=='?') c1='a';

                        else c1=c2;

                    }

                    strcpy(g[p2][i]+1,g[p0][i+1]);

                    k=f[p0][i+1];

                    g[p2][i][0]=g[p2][i][k+1]=c1;

                    g[p2][i][k+2]=0;

                    f[p2][i]=k+2;

                }

            }

        }

        p0=p1;

        p1=p2;

        p2=3^p0^p1;

    }

    if(f[p1][0]<800)

    {

        puts("YES");

        puts(g[p1][0]);

    }

    else

    {

        puts("NO");

    }

    return 0;

}