WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
BZOJ 5439: 字符串
BZOJ 5439: 字符串

Description

对于字符串s,若它的长度为n,最小循环节长度为m,那么我们定义它的价值为\frac{n^2}{m}
给定一个只包含a,b,c的字符串,求它的价值最大的非空子序列的价值。
有多组数据。

Input

第一行一个整数T表示数据组数。
每组数据第一行一个整数n,第二行一个长度为n的字符串。
T\leq 10, 1\leq n\leq 10^5

Output

每组数据输出一行一个整数表示答案。

Sample Input

1
11
abcabacbcac

Sample Output

18

题解

因为字符集很小只有3,所以我们先考虑最小循环长度为1的那些子序列:aa\cdots a,bb\cdots b, cc\cdots c。这三种子序列的答案的最大值肯定不小于\frac{n^2}{9}

因为求一个最大值,所以接下来我们只需要考虑最小循环长度为2\cdots 8的那些才有意义。

对于每种最小循环长度,我们3^m生成最小循环串,然后放到原串中进行DP,求出最大价值。

这样会超时,但是我们又可以发现,如果最小循环串长度较长的话,在原串的子序列进行匹配时要求就更加严格(不能失配太多次)。所以,我们进行剪枝,计算一个最小循环串在原串的子序列中匹配到某个状态是最少失配字符数量,如果超过能够接受的失配上界就终止DP。

不过,从过题时间上来看,似乎有其他神仙做法呀。Emmmmm

/**
* Author : WNJXYK
* Date : 20180824
* Problem : BZOJ 5439
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const LL MOD=998244353;
const int MAXN=1e5+50;

LL Abs(LL x) {return x<0?-x:x;}
LL Pow(LL a, LL b) {LL res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
LL Gcd(LL a, LL b) {return b?Gcd(b,a%b):a;}

char str[MAXN];
int n;
int cnt[MAXN][5];
LL ans=0;

char S[10];
int C[5], dp[MAXN][10];

inline int get(int l, int r, int c){
    return cnt[r][c]-cnt[l-1][c];
}

LL calc(int m, int bury){
    C[0]=C[1]=C[2]=0;
    for (int k=0; k<m; k++) dp[0][k]=-1, ++C[S[k]-'a'];
    for (int i=1; i<=n; i++){
        int miBury=n, baseBury=0, exc=0;
        exc=(n-i+1)/m;
        for (int k=0; k<3; k++) baseBury+=max(0, get(i, n, k)-exc*C[k]);
        for (int k=0; k<m; k++){
            dp[i][k]=dp[i-1][k];
            miBury=min(miBury, i-1-dp[i-1][k]);
        }
        if (miBury+baseBury>bury) return 0;
        for (int k=0; k<m; k++){
            if (str[i]==S[k]) {
                if (k==0){
                    dp[i][k]=max(dp[i][k], max(1, dp[i-1][m-1]+1));
                }else{
                    if (dp[i-1][k-1]!=-1) dp[i][k]=max(dp[i][k], dp[i-1][k-1]+1);
                }
            }
        }
        //printf("#%d %d %d\n", i, dp[i][0], dp[i][1]);
    }
    return 1LL*dp[n][m-1]*dp[n][m-1]/m;
}


inline void solve(int T){
    ans=0;
    scanf("%d%s", &n, str+1);

    // M=1
    cnt[0][0]=cnt[0][1]=cnt[0][2]=0;
    for (int i=1; i<=n; i++) {
        for (int k=0; k<3; k++) cnt[i][k]=cnt[i-1][k];
        ++cnt[i][str[i]-'a'];
    }
    for (int i=0; i<3; i++) ans=max(ans, 1LL*cnt[n][i]*cnt[n][i]);

    // M=2
    S[0]='a'; S[1]='b'; S[2]='c';
    do{
        ans=max(ans, calc(2, n));
    }while(next_permutation(S, S+3));

    // M>=3
    for (int l=3; ans*l<1LL*n*n; l++){
        for (int i=0; i<l; i++) S[i]='a';
        int bury=n-(int)sqrt(ans*l); //printf("%d %d\n", l, bury);
        while(true){
            ans=max(ans, calc(l, bury));
            int j=l-1;
            while(j>=0 && S[j]=='c') j--;
            if (j<0) break;
            S[j]++;
            for (int i=j+1; i<l; i++) S[i]='a';
        }
    }

    printf("%lld\n", ans);
}

int main(){
    //freopen("in.txt" ,"r", stdin);
    // freopen("out.txt", "w", stdout);
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    // solve(0);
    return 0;
}

赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

BZOJ 5439: 字符串
Description 对于字符串$s$,若它的长度为$n$,最小循环节长度为$m$,那么我们定义它的价值为$\frac{n^2}{m}$。 给定一个只包含a,b,c的字符串,求它的价值最大的非空子序列的价值。 有多…
扫描二维码继续阅读
2018-08-24
<--! http2https -->