自动搬运

查看原文

来自洛谷，原作者为

	wangwang0307 wangwang!!! 一只普普通通的……

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

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

以下是正文

思路

可以用动态规划做。

我们设传进来的字符串为 $a$。

状态：$f_{i,j}$ 表示在字符串中两个分别以 $a_i$ 和 $a_j$ 开头的两个子串能匹配（指能使得 $a_{i\ldots i+f_{i,j}}$ 与 $a_{j\ldots j+f_{i,j}}$ 互反）的最大长度。

状态转移方程：当 $a_i$ 与 $a_j$ 不等时即是 $f_{i+1,j+1}+1$（也就是在 $a_i$、$a_j$ 之后一个数 $a_i+1$、$a_j+1$ 开头能最大匹配的长度加 $1$），否则就是没有匹配，即为零。

AC CODE

#include<iostream>
#include<queue>
#include<utility>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<string>
#include<climits>
#include<vector>
namespace noip {
	using Int=long long;
	constexpr Int Max_N=1000;
	char a[1+Max_N];
	Int f[1+Max_N][1+Max_N]{};
	void init(){}
	void main(){
		std::cin>>a;Int n=std::strlen(a);
		for(Int i=n;i--;){
			for(Int j=n;j--;){
				f[i][j]=a[j]!=a[i]?1+f[i+1][j+1]:0;
			}
		}
		Int ans=0;
		for(Int i=0;i<n;i++){
			for(Int j=i+1;j<n;j++){
				ans+=std::min(j-i,f[i][j]);//防止计算的两个子串重叠,因为题目要求 b 小于 c 
			}
		}
		std::cout<<ans<<std::endl;
	}
}
int main(){
	noip::init();
	noip::main();
	return 0;
}