一句,剪枝很重要!
  • A的代码:北大真是福地呀!随便A,连goto这种垃圾也能过,哈哈哈!
Memory: 256K

Time: 125MS

Language: C++

Result: Accepted

 

 

#include <iostream>

using namespace std;

const int MAXLEN = 10,MAXPTS = 10,MAXVALUE = 30000;

int n,a[MAXPTS],b[MAXPTS],cmd[MAXLEN],bestcmd[MAXLEN];
int caseno=1,bestlen;
char *cmdstr[5] = { "ADD", "DIV", "DUP", "MUL", "SUB" };

void try1(int step, int stack, int *s[])
{
  int i,c,sn[MAXPTS],*tmp;
  if(step >= bestlen) return;//看到"剪刀"的作用了,很强大的地方,快了不少

  for(i=0;i<n;i++)
    if(b[i] != s[stack][i]) break;
  if(i == n)
    {
      bestlen = step;memcpy(bestcmd,cmd,sizeof(int)*step);
      return;
    }
  if(step == MAXLEN) return;

  for(c=0;c<5;c++)
    {
      if(c != 2 && stack < 1) continue;
      //if(c == 2 && stack > MAXLEN-1-step) continue;
      cmd[step] = c;
      if(c==0){for(i=0;i<n;i++) sn[i] = s[stack-1][i] + s[stack][i];}
      else if(c==1){
for(i=0;i<n;i++)
    if(s[stack][i] == 0)  goto skip;
    else  sn[i] = s[stack-1][i] / s[stack][i];
      }else if(c==2){
tmp = s[stack+1]; s[stack+1] = s[stack];
try1(step+1,stack+1,s);
s[stack+1] = tmp;
      }else if(c==3){
  for(i=0;i<n;i++) sn[i] = s[stack-1][i] * s[stack][i];
      }else if(c==4){
  for(i=0;i<n;i++) sn[i] = s[stack-1][i] s[stack][i];
      }
      for(i=0;i<n;i++)
         if(abs(sn[i])>MAXVALUE) goto skip;
      tmp = s[stack-1],s[stack-1] = sn;
      try1(step+1,stack-1,s);//keep stack-1 here!
      s[stack-1] = tmp;
      skip: ;
    }
}

void process_data()
{
  int *s[MAXPTS],i;

  s[0] = a;
  bestlen = MAXLEN + 1;
  try1(0,0,s);

  cout<<"Program "<<(caseno++)<<endl;
  if(bestlen > MAXLEN)
    cout<<"Impossible";
  else
    if(bestlen == 0)
      cout<<"Empty sequence";
    else
      for(i=0;i<bestlen;i++){
         cout<<cmdstr[bestcmd[i]];
         if(i!=bestlen-1)cout<<" ";
      }
  cout<<endl<<endl;
}

int main(){
    int i=0;
    while(cin>>n&&n){
        for(i=0; i<n; i++) cin>>a[i];
        for(i=0; i<n; i++) cin>>b[i];
        process_data();
    }
    return 0;
}

  • 被浙大ACM鄙视的代码:完全看不出问题,呵呵!用个bool来控制循环![换成int,居然过了,俄!!]

#include <fstream>
#include <iostream>
using namespace std;

//backup data
const int MaxSize=30,MAXVALUE=30000,cmdn=5,MAXSK=10,thre=10;
//stack is smaller than before
int a[MaxSize],b[MaxSize],cur=1;
int bestcmd[thre],cmd[thre];
char* cmdstr[cmdn]={"ADD", "DIV", "DUP", "MUL", "SUB"};
//for track and dfs
void track(int n);
void dfs(int sk, int cmdnum, int* stk[], int& bestnum, const int&n);

void dfs(int sk, int cmdnum, int* stk[], int& bestnum, const int&n){
    if(sk<0||cmdnum>=bestnum) return;//cut-off branches
    int k=0;
    for(;k<n;k++) if(stk[sk][k]!=b[k]) break;
    if(k==n){//cut-off branches
        bestnum=cmdnum;
        memcpy(bestcmd,cmd,sizeof(int)*cmdnum);
    }
    int s[MAXSK],c,i,*tmp;
    bool skip=false;
    for(c=0;c<cmdn;c++){
        if(sk==0&&c!=2) continue;
        cmd[cmdnum]=c,skip=false;//avoid to access unnecessary array
        //if(c==2&&cmdnum+sk+1>thre)continue;
        if(c==0){//ADD
            for(i=0;i<n;i++){
                s[i]=stk[sk-1][i]+stk[sk][i];
                if(s[i]>MAXVALUE||s[i]<-1*MAXVALUE){skip=true;break;}
            }
        }
        else if(c==1){
            for(i=0;i<n;i++){
                if(stk[sk][i]==0){skip=true;break;}//server bugs here
                s[i]=stk[sk-1][i]/stk[sk][i];
                if(s[i]>MAXVALUE||s[i]<-1*MAXVALUE){skip=true;break;}
            }
        }
        else if(c==2){
            tmp=stk[sk+1],stk[sk+1]=stk[sk];//here,backup the modified item
            dfs(sk+1,cmdnum+1,stk,bestnum,n);
            stk[sk+1]=tmp;
        }
        else if(c==3){
            for(i=0;i<n;i++){
                s[i]=stk[sk-1][i]*stk[sk][i];
                if(s[i]>MAXVALUE||s[i]<-1*MAXVALUE){skip=true;break;}
            }
        }
        else if(c==4){
            for(i=0;i<n;i++){
                s[i]=stk[sk-1][i]-stk[sk][i];
                if(s[i]>MAXVALUE||s[i]<-1*MAXVALUE){skip=true;break;}
            }
        }
        if(!skip){//skip=false;
            tmp=stk[sk-1],stk[sk-1]=s;
            dfs(sk-1,cmdnum+1,stk,bestnum,n);
            stk[sk-1]=tmp;
        }
    }
}

void track(int n){
    int bestnum=thre+1, *stk[MAXSK], i;
    stk[0]=a;
    dfs(0, 0, stk, bestnum, n);
    cout<<"Program "<<(cur++)<<endl;
    if(bestnum==0) cout<<"Empty Sequence";
    else if(bestnum<=thre){
        for(i=0; i<bestnum; i++){
            cout<<cmdstr[bestcmd[i]];
            if(i!=bestnum-1)cout<<" ";
        }
    }
    else cout<<"Impossible";
    cout<<endl<<endl;
}

#define fbased
int main(){
    #ifdef fbased
    ifstream in("input.txt");
    if(!in){cerr<<"error to open input file"<<endl; return EXIT_FAILURE;}
    cin.rdbuf(in.rdbuf());
    #endif
    int n,i=0;
    while(cin>>n&&n){
        for(i=0; i<n; i++) cin>>a[i];
        for(i=0; i<n; i++) cin>>b[i];
        track(n);
    }
    return 0;
}
#undef fbased

Advertisements