P9232 [蓝桥杯 2023 省 A] 更小的数

zhlzt · 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;
}