Hills And Valleys 杭电多校第五场

题意：长度为n的序列，有一次翻转区间的机会，问最长不减序列

题解：如果没有翻转区间的机会，有两个做法。

一是dp[i]表示以i结尾的最长序列 dp[i]=max(dp[i],dp[j]+1) (j<=i)。

二是那个抽牌替换的解法。

这道题可以翻转但是值域很小，所以考虑最长子序列和值域的关系。

选择第一种解法改进。

显然不翻转的话是序列A与序列B ={0123456789} 来匹配，B中的元素可以被匹配到多次。

现在要求翻转一次后的最长子序列，直接翻转A的复杂度是C(n,2)*n*10。

考虑有效翻转的意义，一定是将（只有）一个递减的序列变为递增。

这就相当于在被匹配的B序列中插入一个递减序列来被A匹配。

比如A是12345564678，直接匹配的对应的B'序列是12345(64)678,也就是B中多加了一个递减序列。

所以可以不翻转A，翻转B，这样复杂度就将为C(10,2)*n*20。

实现问题的话，可以在第二位数值域上多加10个来记录要添加的递减序列长度。

关于记录位置，因为只需考虑值域，所以只需开两个L[20],R[20]数组来记录以数字i结尾的（每个数分递减递增）左边和右边翻转区域即可。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e5+;

int dp[N][],n,T,len[],L[],R[];

int ans,l,r;

char s[N];

void solve(int ll,int rr){

    int tar;

    for(int i=;i<=n;++i) for(int j=;j<;++j) dp[i][j]=;

    for(int i=;i<;++i) len[i]=;

    for(int i=;i<;++i) L[i]=R[i]=;

    for(int i=;i<=n;++i) {

        tar=s[i]-'';

        for(int j=tar;j>=;--j) {

            if(dp[i][tar]<len[j]+) {

                dp[i][tar]=len[j]+;

                if(L[j]) L[tar]=L[j];else L[tar]=i;

                if(R[j]) R[tar]=R[j];else R[tar]=i;

            }

        }

        if(ll<=tar&&tar<=rr) {

            for(int j=tar+;j<=+rr;++j) {

                if(dp[i][tar+]<len[j]+) {

                     dp[i][tar+]=len[j]+;

                     if(!L[j]) L[tar+]=i;else L[tar+]=L[j];

                     R[tar+]=i;

                }

            }

            for(int j=;j<=ll;++j) if(dp[i][tar+]<len[j]+){

                dp[i][tar+]=len[j]+;

                L[tar+]=R[tar+]=i;

            }

        }

        if(tar>=rr) {

            for(int j=+ll;j<=+rr;++j) {

                if(dp[i][tar]<len[j]+) {

                    dp[i][tar]=len[j]+;

                    L[tar]=L[j],R[tar]=R[j];

                }

            }

        }

        if(dp[i][tar]>ans) ans=dp[i][tar],l=L[tar],r=R[tar];

        if(ll<=tar&&tar<=rr&&ans<dp[i][tar+]) ans=dp[i][tar+],l=L[tar+],r=R[tar+];

        for(int j=;j<;++j) len[j]=max(len[j],dp[i][j]);

    }

}

int main(){

    for(scanf("%d",&T);T--;){

        scanf("%d",&n);

        scanf("%s",s+);

        ans=;

        l=r=;

        for(int i=;i<;++i) for(int j=i+;j<;++j) solve(i,j);

        printf("%d %d %d\n",ans,l,r);

    }

}

巴特西

Hills And Valleys 杭电多校第五场

最新文章

热门文章