自动搬运

查看原文

来自洛谷，原作者为

	zhlzt Light in the eyes.

搬运于2025-08-24 22:46:36，当前版本为作者最后更新于2023-05-20 08:34:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

区间 DP 做法

其实要满足 $num_{new}<nu m$，就相当于判断翻转后的区间是否比原来小，假如翻转的区间为 $[i,j]$，则翻转前后的区间数值是这样的：

$$a_{i}~~a_{i+1}~~a_{i+2}~~\cdots ~~a_{j-2}~~a_{j-1}~~a_{j} $$$$a_{j}~~a_{j-1}~~a_{j-2}~~\cdots ~~a_{i+2}~~a_{i+1}~~a_{i} $$

设双指针 $l=i,r=j$。设 $dp_{i,j}$ 表示翻转的区间为 $[i,j]$ 时是否满足条件。$dp_{i,j}$ 有如下判断方法（可参照上图理解）：

• 若 $l>r$，说明区间 $[i,j]$ 为回文串，翻转前后相等，$dp_{i,j}=0$，退出判断。
• 若 $a_l<a_r$，则当前判断的区间 $[l,r]$ 翻转后的最高位较大，$dp_{i,j}=0$，退出判断。
• 若 $a_l>a_r$，则当前判断的区间 $[l,r]$ 翻转后的最高位较小，$dp_{i,j}=1$，退出判断。
• 若 $a_l=a_r$，则 $a_l,a_r$ 对 $dp_{i,j}$ 的值没有影响，将双指针指向的区间 $[l,r]$ 缩小到 $[l+1,r-1]$，即执行 $l\gets l+1,r\gets r-1$。

如果像上述做法暴力判断的话，复杂度最差为 $O(n^3)$，但经过整合即可得到：

• 若 $a_i<a_j$，则 $dp_{i,j}=0$。
• 若 $a_i>a_j$，则 $dp_{i,j}=1$。
• 若 $a_i=a_j$，则 $dp_{i,j}=dp_{i+1,j-1}$。

这就是区间 DP，复杂度为 $O(n^2)$。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=5010;
char s[maxn];
int dp[maxn][maxn];
int main(){
	scanf("%s",s);
	int n=strlen(s),ans=0;
	for(int i=0;i<n;i++) dp[i][i]=0;
	for(int i=0;i<n-1;i++) dp[i][i+1]=(s[i]>s[i+1]);
	// 初始值
	for(int len=3;len<=n;len++){
		for(int i=0;i<n-len+1;i++){
			int j=i+len-1;
			if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1];
			else if(s[i]>s[j]) dp[i][j]=1;
		}
	}
	for(int i=0;i<n;i++){
		for(int j=i;j<n;j++) ans+=dp[i][j];
	}
	//求总数
	printf("%d\n",ans);
	return 0;
}