1262.cpp

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

#include<iostream>
#include<string>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
void makestd(string & s){
    string temp=s;
	for(int i=1;i<s.length();i++){
       char t=temp[0];
	   temp.erase(&temp[0]);
	   temp.insert(temp.end(),t);
	   if(temp<s) s=temp;
	}
}
int main(){
  //ifstream cin("in.txt");
  int nows,i,j,n,s,p1,p2,p3,f;
  vector<string> change(8);
  string input;
  while(cin>>n){
	 f=0;
	 vector<string> after;
	 vector<int> num;
     cin>>input;
	 for(s=0;s<8;s++) cin>>change[s];
	 cin>>s;
	 makestd(input);
	 after.push_back(input);
	 num.push_back(7);
     for(i=1;i<=s;i++){
         int nows=(i-1)%8;
		 input=after.back();
		 for(j=0;j<n;j++){
             p1=j-2; while(p1<0) p1+=n;
			 p2=j; 
			 p3=j+1; while(p3>=n) p3-=n;
             if(after.back()[p1]==change[nows][0]&&after.back()[p2]==change[nows][1]&&after.back()[p3]==change[nows][2])
				 input[j]=change[nows][3];
		 }
		 makestd(input);
         for(j=0;j<after.size();j++)
			 if(input==after[j]&&nows==num[j]) break;
		 if(j==after.size()){after.push_back(input);num.push_back(nows);}
		 else{
             f=1;
			 cout<<after[(s-j)%(i-j)+j]<<endl;
			 break;
		 }
	 }
/*	 for(i=1;i<=s;i++){
         input=after.back();
		 string temp=input;
		 for(nows=0;nows<8;nows++){
             for(j=0;j<n;j++){
                p1=j-2; while(p1<0) p1+=n;
			    p2=j; 
			    p3=j+1; while(p3>=n) p3-=n;
                if(temp[p1]==change[nows][0]&&temp[p2]==change[nows][1]&&temp[p3]==change[nows][2])
				   input[j]=change[nows][3];
			 }
			 temp=input;
		 }
		 makestd(input);
         for(j=0;j<after.size();j++)
			 if(input==after[j]) break;
		 if(j==after.size()){after.push_back(input);}
		 else{
             f=1;
			 cout<<after[(s-j)%(i-j)+j]<<endl;
			 break;
		 }
	 }*/
	 if(f==0) cout<<after.back()<<endl;
  }
}