猫史档案馆

给出一个长度不超过200的由小写英文字母组成的字母串（该字母串以每行20个字母的方式输入，且保证每行一定为20个）。要求将此字母串分成k份，且每份中包含的单词个数加起来总数最大。每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字母串this中可包含this和is，选用this之后就不能包含th。单词在给出的一个不超过6个单词的字典中。每个单词长度不超过10。要求输出最大的个数。

输入: 第一行有两个正整数p,k。 p表示字母串的行数，k表示分为k个部分。接下来的p行，每行均有20个字符。再接下来有一个正整数s，表示字典中单词个数。接下来的s行，每行均有一个单词。（2 ≤ k ≤ 40，1 ≤ s ≤ 6）

输出: 1个整数，表示题目所求的最大的个数。

输入样例1: 1 3 thisisabookyouareaoh 4 is a ok sab

输出样例1: 7

输入样例2: 2 1 thisisappleisthisthe oopbooktheisurrtoywe 4 is of the book

输出样例2: 8

用时/内存: 1000MS/100MB。

tbadb

输入样例1: 1 3

thisisabookyouareaoh

is a ok sab

输出样例1: 7

输入样例2: 2 1

thisisappleisthisthe

oopbooktheisurrtoywe

is of the book

输出样例2: 8

tbadb

二分查找应该可以吧?

PoskeVH

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int p, k, s, n, len[205], num[205][205], f[205][45];
string str = " ", t, w[10];
bool isWordInStr(const string& s, const string& word, int start)
{
    for (int i = 0; i < word.length(); i++)
    {
        if (s[start + i]!= word[i])
        {
            return false;
        }
    }
    return true;
}
void countWords(int start)
{
    int end = min(start + 10, n + 1);
    for (int i = start; i < end; i++)
    {
        len[i] = 0;
        for (int j = 0; j < s; j++)
        {
            if (isWordInStr(str, w[j], i))
            {
                len[i]++;
            }
        }
    }
}
int dp(int i, int j)
{
    if (f[i][j]!= -1)
    {
        return f[i][j];
    }
    if (j == 0)
    {
        f[i][j] = 0;
        return 0;
    }
    if (i == 0)
    {
        f[i][j] = 0;
        return 0;
    }
    int res = 0;
    for (int l = 0; l < i; l++)
    {
        int temp = dp(l, j - 1) + num[l + 1][i];
        if (temp > res)
        {
            res = temp;
        }
    }
    f[i][j] = res;
    return res;
}

int main()
{
    cin >> p >> k;
    for (int i = 1; i <= p; i++)
    {
        cin >> t;
        str += t;
    }
    n = p * 20;
    cin >> s;
    memset(len, 0x3f, sizeof(len));
    memset(f, -1, sizeof(f));
    for (int i = 0; i < s; i++)
    {
        cin >> w[i];
    }
    for (int i = 1; i <= n; i++)
    {
        countWords(i);
    }
    for (int i = 1; i <= n; i++)
    {
        num[i][i] = len[i];
        for (int j = i + 1; j <= n; j++)
        {
            num[i][j] = num[i][j - 1] + len[j];
        }
    }
    int ans = dp(n, k);
    cout << ans << endl;

    return 0;
}

猫史档案馆

【C++】这题咋做

回复