1452.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<vector>
#include<iostream>
#include<fstream>
using namespace std;
int main(){
   //ifstream cin("in.txt");
   int t,o,e,i,j,k,l,n=0;
   while(cin>>t&&t){
       vector<int> a,b,table(10000,0),use(10000,-1);
	   while(cin>>i&&i) a.push_back(i);
	   while(cin>>i&&i) b.push_back(i);
	   e=o=0;
	   for(k=0;k<t;k++){
		  /* for(i=0;i<a.size();i++){
              cout<<a[i];
			  if(i!=a.size()-1) cout<<" ";
			  else cout<<endl;
		   }
		   for(i=0;i<b.size();i++){
              cout<<b[i];
			  if(i!=b.size()-1) cout<<" ";
			  else cout<<endl;
		   }*/
		   if(a.size()==0||b.size()==0) break;
		   if(o==0){//a先出
               table[e++]=a[0];
			   if(use[a[0]]!=-1){
				   l=use[a[0]];
				   for(i=e-1;i>=l;i--){
                      a.push_back(table[i]);
					  use[table[i]]=-1;
				   }
				   e=i+1;
				   a.erase(&a[0]);
				   o=1;
				   continue;
			   }
			   else{
				   use[a[0]]=e-1;
			       a.erase(&a[0]);
				   o=1;
			   }
		   }
		   else{
               table[e++]=b[0];
			   if(use[b[0]]!=-1){
				   l=use[b[0]];
				   for(i=e-1;i>=l;i--){
                      b.push_back(table[i]);
					  use[table[i]]=-1;
				   }
				   e=i+1;
				   b.erase(&b[0]);
				   o=0;
				   continue;
			   }
			   else{
				   use[b[0]]=e-1;
			       b.erase(&b[0]);
			       o=0;
			   }
		   }
		   
	   }
	   cout<<"Case "<<++n<<":\n";
	   if(a.size()==0) cout<<"B\n";
	   else if(b.size()==0) cout<<"A\n";
	   else {
		   for(i=0;i<a.size();i++){
              cout<<a[i];
			  if(i!=a.size()-1) cout<<" ";
			  else cout<<endl;
		   }
		   for(i=0;i<b.size();i++){
              cout<<b[i];
			  if(i!=b.size()-1) cout<<" ";
			  else cout<<endl;
		   }
		   if(e==0) cout<<"NULL\n";
		   else{
		     for(i=0;i<e;i++){
              cout<<table[i];
			  if(i!=e-1) cout<<" ";
			  else cout<<endl;
			 }
		   }
	   }
   }
   return 0;
}