阿符长命十万岁


私信TA

用户名:uq_31660518827

访问量:1638

签 名:

等  级
排  名 1873
经  验 2588
参赛次数 0
文章发表 13
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

解题思路:

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 人评分

  评论区

  • «
  • »