解题思路:
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 人评分
gets函数前有scanf读取时候,会读取缓存回车导致出错!!!浏览:1100 |
点我有惊喜!你懂得!浏览:1238 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:443 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:722 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:1206 |
数组输出 (C语言代码)浏览:767 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:619 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:554 |
字符串比较 (C语言代码)答案错误????浏览:597 |
C语言考试练习题_排列 (C语言代码)浏览:725 |