补题：HDU多校第五场H题(hdu-6357)——Hills And Valleys

迷南。 2022-05-17 05:44 118阅读 0赞

题目链接：  
[hdu-6357][]

题目大意：  
给你一个长度不超过1e5的序列A，你可以选择一个区间\[l,r\]进行翻转，使得该序列有最长不下降子序列（即非严格递增子序列），输出最长不下降子序列得长度，以及左右翻转端点 l 和 r（这个可能不唯一）

解题思路：  
赛后看视频题解，不太明白，感觉好迷，于是研究上网研究大佬代码，终于迷迷糊糊懂了题解得意思。解释如下：  
首先需要明白的一个大前提是，序列A中只有数字0-9，于是我们可以构造出一个序列  
b=0123456789  
注意：这是一个递增序列，那我们是否可以把该题转换成求A和b的最长公共子序列，但是这里稍微有不同的是，b中的数值i可以多次和A中数值i匹配（即一对多）；因此这里我们每次遇到相同元素时，对应的最长公共子序列都要++。因为b本身是一个递增序列，所有我们可以通过遍历序列A，遇到和b中相同元素就dp\[i\]\[j\]++,然后不断往后更新最大的dp\[i\]\[j\],最后的答案就是dp\[n\]\[cnt-1\] (可参考后面代码）；因为b只有10个元素，枚举才C（2，10）次，所有我们可能通过翻转b，构造出题解样式的新序列b 0,1,2,……x−1,x,(y,y−1,y−2,……，x+1,x),y,y+1,……8,9  
然后得出答案。

那l和r如何求呢？？？  
这里就需要再开两个二维数组记录第一次匹配到x,和最后一次匹配到y的位置了！！！

具体看代码吧：

#include <bits/stdc++.h>
    using namespace std;
    
    const int MAXN=100010;
    char s[MAXN];
    int t,n;
    int b[15];
    int dp[MAXN][15],tl[MAXN][15],tr[MAXN][15];
    int templ,tempr,ansl,ansr,ans;
    
    int solve(int cnt){
        for(int i=0; i<cnt; ++i){
            dp[0][i] = 0;
        }
    
        for(int i=1; i<=n; ++i){
            for(int j=0; j<cnt; ++j){
                //同步更新
                dp[i][j] = dp[i-1][j];
                tl[i][j] = tl[i-1][j];
                tr[i][j] = tr[i-1][j];
                int y=s[i]-'0';
                if(y==b[j]){
                    dp[i][j]++;
                    if(j==templ&&tl[i][j]==0){
                        tl[i][j] = i;
                    }
                    if(j==tempr) tr[i][j] = i;
                }
                //如果上一次的更新使得值域增大，需要往后更新
                if(j-1>=0&&dp[i][j-1]>dp[i][j]){
                    dp[i][j] = dp[i][j-1];
                    tl[i][j] = tl[i][j-1];
                    tr[i][j] = tr[i][j-1];
                }
            }   
        }
        return dp[n][cnt-1];
    }
    
    int main(int argc, char const *argv[])
    {
        scanf("%d",&t);
        while(t--){
            int maxl = 0, minl = 9;
            scanf("%d%s",&n,s+1);
            // 求出序列S的最大最小的数值
            for(int i=1; i<=n; ++i){
                int y=s[i]-'0';
                maxl = max(maxl,y);
                minl = min(minl,y);
            }
            // 初始化b序列（0~9）
            for(int i=0; i<10; ++i) b[i]=i;
            ans = solve(10);
    
            ansl=1;ansr=1;
            //开始枚举翻转序列b，构造出题解的那样的序列，同时需要记录下来左右端点的位置，方便之后记录
            for(int l=minl; l<=maxl; ++l){
                for(int r=minl; r<l; ++r){
                    int cnt=0;
                    for(int i=0; i<=r; ++i)
                        b[cnt++]=i;
                    templ=cnt;
                    for(int i=l;i>=r; --i)
                        b[cnt++]=i;
                    tempr=cnt-1;
                    for(int i=l; i<10; ++i)
                        b[cnt++]=i;
    
                    int ret=solve(cnt);
                    if(ret>ans&&tl[n][cnt-1]&&tr[n][cnt-1]){
                        ans=ret;
                        ansl=tl[n][cnt-1];
                        ansr=tr[n][cnt-1];
                    }
                }
    
            }
            printf("%d %d %d\n",ans,ansl,ansr);
        }
        return 0;
    }

[hdu-6357]: http://acm.hdu.edu.cn/showproblem.php?pid=6357