[模拟赛]戒指 题解

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。

原文链接:https://www.codein.icu/gm1055/

前言

恶心的动态规划,各种奇怪的细节,对着数据调了一个下午才调出来。

题面

描述

S计划送给J一枚戒指,以示他们的爱情天长地久。
同时,S打算在戒指上刻写一些语句,以增加它的寓意。可惜戒指的大小有限,最多只能被刻入N个字母。细心的S非常了解J,知道她喜欢的单词,例如love, forever等等,同时他也知道这些单词都存在一个“愉悦值”,值越高的单词越能取悦J。
现在,S希望刻入一条字符串,使得各个单词在字符串中出现的次数 × 单词愉悦值之和尽可能的大。

输入

首行为一个整数T,表示数据个数。
每组数据第一行为两个整数N、M,分别表示能刻入戒指的字符串长度以及J喜欢的单词个数。
之后为M行,每行为一个单词Si,表示J喜欢的第i个单词。单词仅包含小写字母。
之后一行包含M个正整数Hi,表示第i个单词的取悦值。

  1. 1 <= T <= 15
  2. 1 <= N <= 50,1 <= M <= 100
  3. 1 <= 单词长度 <= 10
  4. 1 <= Hi <= 100
  5. 数据保证不出现重复的单词

输出

对于每组数据输出一行,为在戒指上刻入的字符串。
如果有多解,则输出长度最短的解,若依然有多接则输出字典序最小的解。
答案有可能为空串。

样例

输入:

2
7 2
love
ever
5 5
5 1
ab
5

输出:

lovever
abab

解法

一开始想爆搜,后来发现可以动态规划。
定义 \(f(i,j)\) 为用了前 \(i\) 个字符,最后一个单词为 \(j\) 的最大贡献。
转移时,对于每个 \(f(i,j)\),枚举上一个单词 \(k\),即可从 \(f(i - len(j),k)\) 转移。
听起来似乎很美好,但需要考虑上一个单词的后缀是这个单词前缀的情况。
例如样例中:

love
ever

因此利用 kmp 的思想,预处理出 \(next(i,j)\),代表 \(i\) 的真后缀与 \(j\) 的真前缀的最大相同长度。
对于完全相同的串需要特判处理,否则将会得到 \(next(i,i) = len(i)\)。
题目虽然保证了给出的串不相同,但我们仍可能需要重复加串,因此 \(next(i,i)\) 是必要的。例如:

abab

除此之外,还要求最短、字典序最小。
最短很好处理,在枚举 \(i\) 的过程中更新答案,首先获取的一定是最短的,但字典序非常麻烦。
一开始考虑排序,利用枚举顺序来保证字典序,但由于种种原因,这是错误的。
因此我们可以对每个 \(f(i,j)\) 的状态,保存取得该状态的原串 \(as(i,j)\),在转移时如果值相同,则比较 \(as(i,j)\) 来保证字典序即可。
此外还有空串的情况,转移过程中也要避免从非法状态转移过来,因此需要处理各种边界条件。
为了方便比较字典序使用了 string,用上了多年不用的 iostream,扔掉了数十行的快读板子……
代码又臭又长,各种乱搞,仅供参考吧……
再良心地给出数据:
input
output

//这字典序也太恶心了!!!
//直接存全串乱比乱搞
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast","-funroll-loops")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 110,maxm = 110;
int T,n,m;
int f[maxn][maxm],next[maxm][maxm];
string as[maxn][maxm];
struct node
{
    string ss;
    int val;
    bool operator<(const node &b) const
    {
        return ss < b.ss;
    }
}s[maxm];
int ans,ansi,ansj;
namespace kmp
{
    char s[200];
    int len;
    int pi[maxn];
    inline int solve(int eq)
    {
        for(int i = 2,k = 0;i<=len;++i)
        {
            while(k && s[i] != s[k + 1]) k = pi[k];
            if(s[i] == s[k + 1]) ++k;
            pi[i] = k;
        }
        if(eq && pi[len] == (len - 1) / 2) pi[len] = pi[pi[len]];
        return pi[len];
    }
}
int main()
{
    cin.tie(0), ios::sync_with_stdio(false), cout.tie(0);
    cin >> T;
    while(T--)
    {
        cin >> n >> m;
        for(int i = 1;i<=m;++i) for(int j = 1;j<=m;++j) next[i][j] = 0;
        for(int i = 1;i<=n;++i) for(int j = 1;j<=m;++j) f[i][j] = 0,as[i][j].clear();
        for (int i = 1; i <= m; ++i) cin >> s[i].ss;
        for (int i = 1; i <= m; ++i) cin >> s[i].val;
        std::sort(s + 1,s + 1 + m);
        ans = 0,ansi = ansj = 0;
        for(int i = 1;i<=m;++i)
            for(int j = 1;j<=m;++j)
            {
                kmp::len = 0;
                for (string::iterator it = s[j].ss.begin(); it != s[j].ss.end(); ++it) kmp::s[++kmp::len] = *it;
                kmp::s[++kmp::len] = '\0';
                for (string::iterator it = s[i].ss.begin(); it != s[i].ss.end(); ++it) kmp::s[++kmp::len] = *it;
                next[i][j] = kmp::solve(i == j);
            }
        for (int i = 1; i <= m; ++i) 
        {
            int len = s[i].ss.length();
            if(len > n) continue;
            f[len][i] = s[i].val, as[len][i] = s[i].ss;
            if (f[len][i] > ans || (f[len][i] == ans && as[len][i] < as[ansi][ansj])) ans = f[len][i], ansi = len, ansj = i;
        }
        for (int i = 1; i <= n; ++i) 
            for(int k = 1;k<=m;++k)
                for(int j = 1;j<=m;++j)
                {
                    int len = s[j].ss.length(); 
                    if ((int)(i - len + next[k][j] - s[k].ss.length()) < 0) continue;
                    int nval = f[i - len + next[k][j]][k] + s[j].val;
                    if (f[i][j] < nval) f[i][j] = nval, as[i][j] = as[i - len + next[k][j]][k] + s[j].ss.substr(next[k][j]);
                    else if(f[i][j] == nval)
                    {
                        string ns = as[i - len + next[k][j]][k] + s[j].ss.substr(next[k][j]);
                        if(ns < as[i][j]) as[i][j] = ns;
                    }
                    if (f[i][j] > ans || (f[i][j] == ans && as[i][j] < as[ansi][ansj])) ans = f[i][j], ansi = i, ansj = j;
                }
        cout << as[ansi][ansj] << endl;
    }
    return 0;
}
上一篇:c# – TimeSpan Bug ..?


下一篇:在MySQL中找到“免费”时间