链接：https://www.nowcoder.com/acm/contest/90/D 来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 掌握未来命运的女神 psd 师兄在拿了朝田诗乃的 buff 后决定去实习。 埃森哲公司注册成立于爱尔兰，是一家全球领先的专业服务公司，为客户提供战略、咨询、数字、技术和运营服务及解决方案。他们立足商业与技术的前沿，业务涵盖40多个行业，以及企业日常运营部门的各个职能。凭借独特的业内经验与专业技能，以及翘楚全球的交付网络，他们帮助客户提升绩效，并为利益相关方持续创造价值。埃森哲是《财富》全球500强企业之一，目前拥有约41.1万名员工，服务于120多个国家的客户。于是psd打算去埃森哲公司投一下简历。 于是他用英文写了一篇简历，由于手速太快了以致自己都不知道写了什么。 然而面试官 xwc 一眼就看到了重点：大学打过 ACM！ xwc：“ 听说你很低袄？考你个题： 忽略字母大小写，你这篇简历去掉最长的回文子序列后还有多长？ ” psd 顺手就把这个问题抛给了你。 输入描述:
多组输入，每组输入一个长度不超过 1234 的没空格的字符串，是 psd 的简历。
输出描述:
每组输出一个整数，如题。
示例1 输入
输出
2
示例2 输入
aBc,bAd
输出
2
思路一 先将字符串 中的字母都统一为 大写 或者 小写 然后再弄一个串 保存 原串的反转串
然后求两个串的LCS 就是 原串中的 最长回文子序列
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-6; const int INF = 0x3f3f3f3f; const int maxn = 2e3 + 5; const int MOD = 1e9 + 7; int dp[maxn][maxn]; int main() { string a; while (cin >> a) { int len = a.size(); for (int i = 0; i < len; i++) if (a[i] >= 'a' && a[i] <= 'z') a[i] += 'A' - 'a'; string b = ""; for (int i = len - 1; i >= 0; i--) b += a[i]; CLR(dp); for (int i = 0; i < len; i++) { if (i) { dp[0][i] = dp[0][i - 1]; dp[i][0] = dp[i - 1][0]; } if (a[0] == b[i]) dp[0][i] = 1; if (a[i] == b[0]) dp[i][0] = 1; } for (int i = 1; i < len; i++) { for (int j = 1; j < len; j++) { if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } cout << len - dp[len - 1][len - 1] << endl; } }思路二 也可以不用反转 直接DP 做
dp[i][j] 表示 第i 位 到 第 j 位 的最长回文串的长度 如果 a[i] == b[j] dp[i][j] = dp[i + 1][j - 1] + 2 反之 dp[i][j] = max(dp[i +1][j], dp[i][]j - 1)
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-6; const int INF = 0x3f3f3f3f; const int maxn = 2e3 + 5; const int MOD = 1e9 + 7; int dp[maxn][maxn]; int main() { string a; while (cin >> a) { int len = a.size(); for (int i = 0; i < len; i++) if (a[i] >= 'a' && a[i] <= 'z') a[i] += 'A' - 'a'; CLR(dp); for (int i = len - 1; i >= 0 ; i--) { dp[i][i] = 1; for (int j = i + 1; j < len; j++) { dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); if (a[i] == a[j]) dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2); } } cout << len - dp[0][len - 1] << endl; } }转载于:https://www.cnblogs.com/Dup4/p/9433212.html
相关资源：JAVA上百实例源码以及开源项目