[蓝桥杯 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;
}

原文地址：https://blog.csdn.net/rc85qbte/article/details/137686979

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！