FJNU Fang G and his Friends（状压DP）题解

时间：2021-08-31 23:58:08

Description

    众所周知，fang G 有很多小伙伴，有一天，Fang G 打算带他们去玩有趣的游戏OOXX，这个游戏需要分成两组，有趣的是，每个人互相之间都有一个满意度，大家都想和自己看重的人(excuse me???)一组，却又不希望和另一组拉开差距。
    Fang G
发现，每个队伍能发挥出的能力值和这个队伍之间满意值是相等的，而一个队伍之间满意值定义为每一个人对于这个队伍所有人（注意是所有人哦！！！）满意度总和的总和，而一个人对另外一个人的满意度和他们的名字是有关的，A对B的满意度定义为A名字前缀和B名字后缀的最长公共前缀（其实就是首x尾o相x连o辣）。
    而Fang G要做的就是如何分为两队，使得ooxx更加精彩！但是Fang G 现在有事情要做（是什么事情呢？），没办法完成分配工作，你现在就要帮他完成这个伟大的使命！使得两队在能力值差值最小的情况下，能力值较低的那一队满意度尽量高。

Input

第一行输入一个T代表测试数据的组数(T<=10)
接下来每组测试数据里：
第一行输入一个n代表待分队的人数(1<=n<=20)
接下来有n行，每行有一个字符串si代表每个人的姓名0<|si|<=10000

Output

对于每组测试数据，输出一行，从小到大输出两个数字分别代表两只队伍的能力值，两个数字之间用空格隔开

Sample Input

1

3

aab

bbc

cca

Sample Output

3 7

思路：KMP能求出互相之间的满意度。然后我们要遍历所有可能。遍历的复杂度O(2 ^ n)，但是如果我们用n * n的复杂度去判断每一种情况每队的满意度会超时。我们可以用状压DP。显然一共1 << n种可能。我们从0开始往1 << n - 1判，最低位出现的1一定是新变化的，那么我就可以直接算出原来的情况+新增一个最低位的1，达到O（n）算出每队的满意度。

代码：

#include<set>

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include <iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn =  + ;

const ull seed = ;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + ;

char s[][maxn];

int w[][];

int Next[maxn], len[maxn];

int dp[ << ];

int n;

void preKMP(int pos){

    int i = , j = -;

    Next[] = -;

    while(i < len[pos]){

        while(j != -  && s[pos][i] != s[pos][j]) j = Next[j];

        ++i;++j;

        Next[i] = j;

    }

}

int KMP(int p, int str){

    int i = , j = ;

    while(i < len[str]){

        while(j != -  && s[p][j] != s[str][i]) j = Next[j];

        ++j;

        ++i;

        if(i == len[str]) return j;

        if(j >= len[p]){

            j = Next[j];

        }

    }

    return ;

}

int dis, ans1, ans2;

int main(){

    int t;

    scanf("%d", &t);

    while(t--){

       scanf("%d" ,&n);

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

            scanf("%s", s[i]);

            len[i] = strlen(s[i]);

       }

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

            preKMP(i);

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

                if(j == i){

                    w[i][j] = len[i];

                    continue;

                }

                w[i][j] = KMP(i, j);

            }

       }

       memset(dp, , sizeof(dp));

       int mx = ( << n) - ;

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

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

                if(i & ( << j)){

                    for(int k = j + ; k < n; k++){

                        if(i & ( << k)){

                            dp[i] += w[j][k] + w[k][j];

                        }

                    }

                    dp[i] += dp[i - ( << j)] + w[j][j];

                    break;

                }

            }

       }

       dis = INF;

       ans1 = -INF, ans2 = -INF;

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

            if(abs(dp[i] - dp[mx ^ i]) < dis){

                dis = abs(dp[i] - dp[mx ^ i]);

                ans1 = min(dp[i], dp[mx ^ i]);

                ans2 = max(dp[i], dp[mx ^ i]);

            }

            else if(abs(dp[i] - dp[mx ^ i]) == dis){

                int r1 = min(dp[i], dp[mx ^ i]);

                int r2 = max(dp[i], dp[mx ^ i]);

                if(r1 > ans1){

                    ans1 = r2, ans2 = r2;

                }

            }

       }

       printf("%d %d\n", ans1, ans2);

    }

    return ;

}

相关文章