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