Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

DP16ms水果,水题就各种套STL了

Posted by KatrineYang at 2016-08-30 02:05:45 on Problem 1229 and last updated at 2016-08-30 02:06:10
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
using namespace std;

int main() {
	int N;
	cin >> N;
	for(int ii = 0; ii < N; ii++){
		string s1, s2;
		cin >> s1 >> s2;
		s1 += '.', s2 += '.';
		int l1 = s1.length(), l2 = s2.length();
		vector<string> vs1, vs2;
		int cur = -1, next = 0;
		while(next < l1){
			while(s1[next] != '.') next++;
			string tar = s1.substr(cur+1, next-cur-1);
			if(tar == "!"){
				vs1.push_back("#");
				vs1.push_back("#");
				vs1.push_back("*");
			}
			else if(tar == "?"){
				vs1.push_back("#");
				vs1.push_back("&");
				vs1.push_back("&");
			}
			else vs1.push_back(tar);
			cur = next;
			next = cur+1;
		}
		cur = -1, next = 0;
		while(next < l2){
			while(s2[next] != '.') next++;
			string tar = s2.substr(cur+1, next-cur-1);
			if(tar == "!"){
				vs2.push_back("#");
				vs2.push_back("#");
				vs2.push_back("*");
			}
			else if(tar == "?"){
				vs2.push_back("#");
				vs2.push_back("&");
				vs2.push_back("&");
			}
			else vs2.push_back(tar);
			cur = next;
			next = cur+1;
		}
		int m = vs1.size(), n = vs2.size();
		//for(int i = 0; i < m; i++) cout << vs1[i] << " "; cout << endl;
		//for(int i = 0; i < n; i++) cout << vs2[i] << " "; cout << endl;
		bool dp[800][800];
		dp[0][0] = 1;
		for(int i = 1; i < n; i++) dp[0][i] = 0;
		for(int i = 1; i < m; i++) dp[i][0] = 0;
		for(int i = 1; i <= m; i++){
			for(int j = 1; j <= n; j++){
				string s = vs1[i-1], t = vs2[j-1];
				if(s == "*" && t == "*") dp[i][j] = dp[i-1][j-1] || dp[i-1][j] || dp[i][j-1];
				else if(s == "*" && t == "#") dp[i][j] = dp[i-1][j-1] || dp[i][j-1];
				else if(s == "*" && t == "&") dp[i][j] = dp[i-1][j-1] || dp[i][j-1];
				else if(s == "#" && t == "*") dp[i][j] = dp[i-1][j-1] || dp[i-1][j];
				else if(s == "#" && t == "#") dp[i][j] = dp[i-1][j-1];
				else if(s == "#" && t == "&") dp[i][j] = dp[i][j-1] || dp[i-1][j-1];
				else if(s == "&" && t == "*") dp[i][j] = dp[i-1][j-1] || dp[i-1][j];
				else if(s == "&" && t == "&") dp[i][j] = dp[i-1][j-1] || dp[i-1][j] || dp[i][j-1];
				else if(s == "&" && t == "#") dp[i][j] = dp[i-1][j] || dp[i-1][j-1];
				else if(s == "*") dp[i][j] = dp[i-1][j-1] || dp[i][j-1];
				else if(t == "*") dp[i][j] = dp[i-1][j-1] || dp[i-1][j];
				else if(s == "#" || t == "#") dp[i][j] = dp[i-1][j-1];
				else if(s == "&") dp[i][j] = dp[i-1][j] || dp[i-1][j-1];
				else if(t == "&") dp[i][j] = dp[i][j-1] || dp[i-1][j-1];
				else if(s == t) dp[i][j] = dp[i-1][j-1];
				else dp[i][j] = 0;
			}
		}
		if(dp[m][n]) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator