1500.cpp

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

#include<iostream>
#include<fstream>
#include<string>
#include<algorithm>
using namespace std;
int makec(int b,int t){
     int res=1;int i;
	 for(i=b;i>b-t;i--)
        res*=i;
	 for(i=1;i<=t;i++)
		 res/=i;
	 return res;
}
void deal(string s1,string s2,int m,int & r){
     int i,j,k=0; char c;
     for(i=0;i<s1.length();){
        k++;
		c=s1[i];
		j=find(s2.begin(),s2.end(),c)-s2.begin();
        string ss1=s1.substr(i+1,j-i),ss2=s2.substr(i,j-i);
		if(ss1!=ss2)
           deal(ss1,ss2,m,r);
		else r*=makec(m,j-i);
		i=j+1;
	 }
	 r*=makec(m,k);
}
int main(){
    //ifstream cin("in.txt");
	int m;
	int r;
	string s1,s2;
	while(cin>>m&&m){
        cin>>s1>>s2;
		s1.erase(&s1[0]);
		s2.erase(s2.end()-1);
		r=1;
		deal(s1,s2,m,r);
		cout<<r<<endl;
	}
	return 0;
}