1286.cpp

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

#include<iostream>
#include<fstream>
#include<string>
using namespace std;
bool slump(string s);
bool slimp(string s);
int main(){
  //ifstream cin("in.txt");
  int f,n,i;
  string s,s1,s2;
  cout<<"SLURPYS OUTPUT\n";
  cin>>n;
  for(i=0;i<n;i++){
     f=0;
     cin>>s;
	 for(int j=1;j<s.length();j++){
        s1=s.substr(0,j);s2=s.substr(j,s.length()-j);
		//cout<<s1<<" "<<s2<<endl;
		if(slimp(s1)&&slump(s2)) {f=1;break;}
	 }
	 //if(slimp(s)&&slump("")) f=1;
	 if(f) cout<<"YES\n";
	 else cout<<"NO\n";
  }
  cout<<"END OF OUTPUT\n";
}
bool slump(string s){
  if(s.length()==0) return 0;
  if(s.length()==1) return 0;
  if(s[0]!='E'&&s[0]!='D'||s[1]!='F') return 0;
  int i=1;
  while(i<s.length()&&s[i]=='F') i+=1;
  if(i==s.length()) return 0;
  if(s[i]=='G'){
      if(i==s.length()-1) return 1;
	  else return 0;
  }
  else{
      string temp=s.substr(i,s.length()-i);
	  if(slump(temp)) return 1;
	  else return 0;
  }
}
bool slimp(string s){
  if(s.length()==0) return 0;
  if(s.length()==1) return 0;
  if(s[0]!='A') return 0;
  if(s.length()==2){
     if(s[1]=='H') return 1;
	 else return 0;
  }
  if(s.length()>2){
     if(s[s.length()-1]!='C') return 0;
	 else{
		 if(s[1]=='B'){
              string temp=s.substr(2,s.length()-1-2);
			  if(slimp(temp)) return 1;
			  else return 0;
		 }
		 else{
            string temp=s.substr(1,s.length()-1-1);
			  if(slump(temp)) return 1;
			  else return 0;
		 }
	 }
  }
}