1341.cpp

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

#include<vector>
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
vector<string> num;
bool match(string s,vector<int> & broke,int p){
    for(int i=0;i<7;i++){
       if(s[i]=='Y'&&(num[p][i]=='N'||broke[i]==1)) return 0;
	   if(s[i]=='N'&&num[p][i]=='Y') broke[i]=1;
	}
	return 1;
}
bool can(vector<string> vec,int s){
    vector<int> broke(7,0);
	for(int i=0;i<vec.size();i++){
       if(!match(vec[i],broke,s))
		   return 0;
	   s--;
	}
	return 1;
}
int main(){
	//ifstream cin("in.txt");
    int i,j,n;
	num.resize(10);
	num[0]="YYYYYYN";
	num[1]="NYYNNNN";
	num[2]="YYNYYNY";
	num[3]="YYYYNNY";
	num[4]="NYYNNYY";
	num[5]="YNYYNYY";
	num[6]="YNYYYYY";
	num[7]="YYYNNNN";
	num[8]="YYYYYYY";
	num[9]="YYYYNYY";
	while(cin>>n&&n){
       vector<string> vec(n);
	   for(i=0;i<n;i++) cin>>vec[i];
	   for(i=9;i>=n-1;i--){
		   //cout<<i<<endl;
           if(can(vec,i)){
              cout<<"MATCH\n";
			  break;
		   }
	   }
	   if(i==n-2) cout<<"MISMATCH\n";
	}
}