字符串划分 [Bitset 字符串Dp]

$字符串划分$字符串划分

$Description$Description

$Solution$Solution

$贪心$贪心 求出最少划分为 $min\_div$min_div 段, 可以使用 $26$26 个字母的 前缀和 实现.

定义 $dp[i,j]$dp[i,j] 表示前 $i$i 个字母, 分成 $j$j 个区间时的 最优分解状态 (使用 $bitset$bitset 存储)

状态具体地说就是 长度 为 $i$i 的 $0,1串$0,1串, 若 $0,1串$0,1串 中一个位置的值为 $1$1, 表示在该位置后 分配一个分界线 .

则 $O\left(N^3\right)$O(N3) 枚举 $i,j,k$i,j,k, 进行 状态转移, 在 $k$k 位置后切一刀,
将 $dp[k-1,j-1]与...\left(此为位置k\right)\mathrm{1000...}合并为状态T,$dp[k−1,j−1]与...(此为位置k)1000...合并为状态 T,
$将T与dp[i,j]进行比较,取最优值\left[比较需要复杂度O\right(nlogn\left)\right]$将 T 与dp[i,j]进行比较,取最优值  [比较需要复杂度O(nlogn)]

$\therefore$∴ 总复杂度 $O\left(N^{4}logn\right)$O(N4logn)

$Codewithbug$Code with bug

#include<bits/stdc++.h>
#define reg register
#define pb push_back

const int maxn = 55;

int N;
int min_d;
int sum[maxn][30];

std::string debug = "0000101000010010010001000001000000101001100";

char S[maxn];

std::bitset <maxn> dp[maxn][maxn];
std::bitset <maxn> T;

std::string s_1[maxn], s_2[maxn];

bool Used[maxn][maxn];

void Cmp(int a, int b){
        int cnt_1 = 1, cnt_2 = 1;
        for(reg int i = 1; i <= N; i ++) s_1[i] = s_2[i] = "";
        for(reg int i = 1; i <= N; i ++){
                s_1[cnt_1].pb(S[i]); 
                s_2[cnt_2].pb(S[i]);
                cnt_1 += dp[a][b][i];
                cnt_2 += T[i];
        }
        std::sort(s_1+1, s_1+cnt_1+1);
        std::sort(s_2+1, s_2+cnt_2+1);
        bool flag = 0;
        for(reg int i = 1; i <= cnt_1; i ++)
                if(s_2[i] < s_1[i]){ flag = 1; break ; }
        if(flag) dp[a][b] = T;

        /* flag = 1; for(reg int i = 1; i <= N; i ++) if(debug[i]-'0' != T[i]) flag = 0; if(flag) printf("Why\n"); */

}

bool chk(int l, int r){
        for(reg int i = 1; i <= 26; i ++)
                if(sum[r][S[i]-'a'+1] - sum[l-1][S[i]-'a'+1] > 1) return false;
        return true;
}


void Greedy(){ 
        min_d = 0;
        memset(sum, 0, sizeof sum);
        for(reg int i = 1; i <= N; i ++){
                sum[i][S[i]-'a'+1] ++;
                for(reg int j = 1; j <= 27; j ++) sum[i][j] += sum[i-1][j];
        }
        int lastt = 0;
        for(reg int i = 1; i <= N; i ++)
                if(sum[i-1][S[i]-'a'+1] - sum[lastt-1][S[i]-'a'+1]) min_d ++, lastt = i;
}

void Work(){
        scanf("%s", S+1);
        N = strlen(S+1);

        Greedy(); 

        if(min_d == 0){ printf("%s\n", S+1); return ; }

// printf("min_d: %d\n", min_d);

        memset(Used, 0, sizeof Used);
        for(reg int i = 0; i <= N; i ++) Used[i][0] = 1;
        for(reg int i = 1; i <= N; i ++)
                for(reg int j = 1; j <= std::min(min_d, i); j ++)
                        for(reg int k = i; k >= 1; k --){
                                if(!chk(k, i)) break ;
                                if(!Used[k-1][j-1]) continue ;
 // printf("%d %d %d\n", i, j, k);
                                T = dp[k-1][j-1], T[k-1] = 1;
                                Used[i][j] = 1;
                                if(!dp[i][j].any()) dp[i][j] = T;
                                else Cmp(i, j);
                        }

        int cnt = 1;
        for(reg int i = 1; i <= N; i ++) s_1[i] = "";
        for(reg int i = 1; i <= N; i ++){
                s_1[cnt].pb(S[i]); 
                cnt += dp[N][min_d][i];
        }
/* printf("cnt: %d==============\n", cnt); for(reg int i = 1; i <= N; i ++) printf("%d", (int)dp[N][min_d][i]); printf("\n"); */

        std::sort(s_1+1, s_1+cnt+1);
        for(reg int i = 1; i <= cnt; i ++) std::cout << s_1[i] << " ";
        std::cout << std::endl;
}

int main(){
        freopen("string.in", "r", stdin);
        freopen("string.out", "w", stdout);
        int T;
        scanf("%d", &T);
        while(T --) Work();
        return 0;
}