| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
DP16ms水果,水题就各种套STL了#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator