Abbreviation（HackerRank abbr）

https://vjudge.net/problem/HackerRank-abbr 给你两个字符串a, b， 其中a只有大小写字母，b只有大写字母 现对a有两种操作 1. 如果a[i]为小写，则将a[i]变为大写 (0 < i < a.length() ) 2. 删除a中所有小写的字母 问是否能将a变为b dp[i][j] = 1 表示：a的前i个字母能通过操作，变为b的前j个字母 dp[i][j] = 0 表示：  .........不能.....................   状态转移方程： if dp[i][j]     if toUpper(a[i+1]) == b[i+1]         dp[i+1][j+1] = 1;     if !isUpper(a[i+1])

        dp[i+1][j] = 1;

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <queue> #include <vector> #include <cmath> #include <stack> #include <string> #include <sstream> #include <map> #include <set> #define pi acos(-1.0) #define LL long long #define ULL unsigned long long #define inf 0x3f3f3f3f #define INF 1e18 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; typedef pair<int, int> P; const double eps = 1e-10; const int maxn = 1e6 + 5; const int N = 1e4 + 5; const int mod = 1e8; bool isUpper(char c) { if (c <= 'Z' && c >= 'A') return true; return false; } char toUpper(char c) { if (isUpper(c)) return c; return char(c - 32); } int dp[1005][1005]; int main(void) { std::ios::sync_with_stdio(false); // freopen("in.txt", "r", stdin); string a, b; int T; cin >> T; while (T--) { cin >> a >> b; memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int i = 0; i < a.length(); i++){ for (int j = 0; j <= b.length(); j++){ if (dp[i][j]){ if (j < b.length() && toUpper(a[i]) == b[j]) dp[i + 1][j + 1] = 1; if (!isUpper(a[i])) dp[i + 1][j] = 1; } } } if (dp[a.length()][b.length()]) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }