解题思路:
dotcpp上暴力能过,但acwing上暴力只能过80%,考虑到前一个对比相同时我们要去找下一个对比,所以考虑记忆化搜索,因此想到区间DP,可以知道当a[l] == a[r]时,我们直接判断f[l+1][r-1]就能知道f[l][r]的状态了。
参考代码:
// 区间dp写法 #include <iostream> #include <string> using namespace std; const int N = 5010; string a; bool f[N][N]; int main() { cin >> a; int n = a.size(); int ct = 0; int res = 0; for (int len = 2; len <= n; len++) { for (int l = 0; l < n - len + 1; l++) { int r = l + len - 1; if (a[l] > a[r]) { f[l][r] = true; res++; } else if (a[l] == a[r]) { if (f[l + 1][r - 1]) res++; f[l][r] = f[l + 1][r - 1]; } } } cout << res; return 0; } // 暴力写法 #include <iostream> #include <string> using namespace std; string a; bool rev(int l, int r) { for (int i = l, j = r; i < j; i++, j--) { if (a[i] > a[j]) return true; else if (a[i] < a[j]) return false; } return false; } int main() { cin >> a; int n = a.size(); int ct = 0; for (int len = n; len > 1; len--) { for (int l = 0; l < n - len + 1; l++) { int r = l + len - 1; if (rev(l, r)) ct++; } } cout << ct; return 0; }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:597 |
C语言训练-斐波纳契数列 (C语言代码)浏览:1270 |
【绝对值排序】 (C++代码)浏览:720 |
不容易系列 (C语言代码)浏览:702 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:672 |
简单的a+b (C语言代码)浏览:564 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:1215 |
C语言训练-求1+2!+3!+...+N!的和 (C语言代码)浏览:821 |
WU-复数求和 (C++代码)浏览:2119 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:701 |