[蓝桥杯 2023 省 A] 更小的数(dp基础应用）

来源

洛谷P9232

本题dp思想

dp主要思想是：在同一类问题模型下，依赖于已经解决的简单问题基础上，用很小的代价获得更复杂一点的问题的解决方案。
有的题的DP是在下标上顺序性递推的，类似于dp[i]=dp[i-1]+something；
然而这道题的DP是在子串长度上的顺序性递推，而不是在下标上的顺序性递推。

过程

首先算出所有长度为2的子串的dp值，即所有的dp[i][i+1]，然后长度依次从3，4，……递增到n，每一个区间从i到j的子串，他们的dp值意味着可否反转这一段的子串，dp=0不可翻转，dp=1可翻转。

对于长度为len的子串，左右下标分别为i和j

$$d{p}_{(i,j)}=\{\begin{array}{ll}1,& \text{if }str[i]>str[j]\\ 0,& \text{if }str[i]<str[j]\\ d{p}_{(i+1,j-1)},& \text{if }str[i]=str[j]\end{array}$$

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define For for(int i=1;i<=n;i++)
#define rFor for(int i=n;i>0;i--)
#define rep(i,sta,end) for(int i=sta;i<=end;i++)
#define rrep(i,end,sta) for(int i=end;i>=sta;i--)
#define ALL(x) for(auto item:x)
#define int long long
//#pragma GCC optimize(3,"Ofast","inline")


inline void solve() {
	string str;
	cin >> str;
	int n = 1LL*str.size();
	vector<vector<int> > arr;
	rep(i,0,n){
		vector<int> tmp;
		rep(j,0,n){
			tmp.emplace_back(0);
		}
		arr.emplace_back(tmp);
	}
	rep(i,0,n-2){
		arr[i][i+1]=(str[i]>str[i+1]);
	}
	rep(len,3,n){
		rep(i,0,n-len){
			int j=i+len-1;
			if(str[i]==str[j]){
				arr[i][j]=arr[i+1][j-1];
			}else arr[i][j]=(str[i]>str[j]);
		}
	}
	int cot=0;
	rep(i,0,n-1){
		rep(j,i+1,n-1){
			cot+=arr[i][j];
		}
	}
	cout << cot << endl;
}
int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int num = 1LL;
	//cin>>num;
	while (num--)
	{
		solve();
		//cout<<"已经执行solve函数"<<endl;
	}
	return 0LL;
}