解题思路:
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语言程序设计教程(第三版)课后习题12.6 (C语言代码)浏览:794 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:662 |
C语言训练-数字母 (C语言代码)浏览:585 |
这可能是一个假的冒泡法浏览:993 |
printf基础练习2 (C语言代码)浏览:646 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:642 |
C语言程序设计教程(第三版)课后习题8.7 (C语言代码)浏览:916 |
出圈】指针malloc版浏览:355 |
printf基础练习2 (C语言代码)浏览:508 |
C二级辅导-温度转换 (C语言代码)浏览:732 |