ACM模版

描述

题解

这个题的 dp 思维很简单，设 dp[i][j] 表示前 i 个字符分成 j 份的最优解，不过对于任意区间 [i,j] 的单词数就是一个问题了，一开始没有想通这里怎么搞，所以就否定了这种 dp 思路，恐怕搞不定它，后来发现数据如此之小，单词不超过 6 个，字符串长度不超过 200，简直就是为暴力而生，于是暴力一发，求出任意区间的 val[][]，dp 搞搞竟然 AC 了，太诧异了……做习惯了 51Nod，总是不由自主的否定了暴力的思维，实在是不应该啊！

代码

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int MAXN = 222;
const int MAXM = 9;

int P, K, n;
int val[MAXN][MAXN];
int dp[MAXN][MAXN];
int vis[MAXN];
char s[MAXN];
char w[MAXM][MAXN];

int main()
{
    scanf("%d%d\n", &P, &K);

    int cnt = 0;
    for (int i = 1; i <= P; i++)
    {
        for (int j = 0; j < 20; j++)
        {
            scanf("%c", &s[++cnt]);
        }
        getchar();
    }
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", w[i]);
    }

    for (int i = 1; i <= cnt; i++)
    {
        for (int j = i; j <= cnt; j++)
        {
            memset(vis, 0, sizeof(vis));
            for (int k = 1; k <= n; k++)
            {
                int len = (int)strlen(w[k]);
                for (int o = i; o <= j - len + 1; o++)
                {
                    if (vis[o])
                    {
                        continue;
                    }
                    bool flag = 1;
                    for (int p = 0; p < len; p++)
                    {
                        if (s[o + p] != w[k][p])
                        {
                            flag = 0;
                            break;
                        }
                    }
                    if (flag)
                    {
                        val[i][j]++;
                        vis[o] = 1;
                    }
                }
            }
        }
    }

    for (int k = 1; k <= K; k++)
    {
        for (int i = 1; i <= cnt; i++)
        {
            for (int j = k - 1; j <= i - 1; j++)
            {
                dp[i][k] = max(dp[i][k], dp[j][k - 1] + val[j + 1][i]);
            }
        }
    }

// cout << s + 1 << '\n';
    printf("%d\n", dp[cnt][K]);

    return 0;
}