题解：P1026 [NOIP 2001 提高组] 统计单词个数

· · 题解

解题思路：

直接暴力：

直接暴力枚举 k 部分的方案，再求最大值，发现会 TLE。

正解（区间 DP）：

首先用 dp_{i,k} 表示前 i 个数形成了 k 段数字的最大答案，再 init 函数预处理 pre[l,r]，最后通过离线算法处理单词个数（STL 中字符串 find 函数），三重循环即可。

状态转移方程：dp_{i,k}=\max(dp_{i,k},dp_{j,k-1}+pre_{j+1,i})；

设字符串长度为 n，这个转移是 O(n^2k) 的。

坑点：可能同一个位置会有多个单词开始，但是只计数一个单词。

1 2
then
2
the 
then

答案应该是 1。

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
string str, s;
int p, k, n, x;
vector<string> v;
int dp[202][44];
int pre[202][202];

inline bool check(int l, int r) {
    string tem = s.substr(l, r - l + 1);
    for(auto x : v) {
        if(r - l + 1 >= x.size()) {
            if(tem.find(x) == 0) return 1;
        } 
    }
    return 0;
}

void init() {  // 预处理pre[l, r]
    for(int r = n; r >= 1; r--) {    // r 也可以从前往后
        for(int l = r; l >= 1; l--) {
            pre[l][r] = pre[l + 1][r];
            if(check(l, r)) pre[l][r]++; 
        }
    }
}

int main() {
    cin >> x >> k;
    while(x--) {
        cin >> str;
        s += str;
    }
    s = " " + s;
    n = s.size() - 1;
    if(k > n - 1) {
        puts("0");
        return 0;
    }
    cin >> p;
    for(int i = 1; i <= p; i++) {
        cin >> str;
        v.push_back(str);
    }

    init();

    for(int K = 1; K <= k; K++) {  // K <= k
        for(int i = 1; i <= n; i++) {  //  i < n
            for(int j = K - 1; j < i; j++) {
                dp[i][K] = max(dp[i][K], dp[j][K - 1] + pre[j + 1][i]);
            }
            // cout << "i: " << i << " k: " << K << "dp[i][K]: " << dp[i][K] << endl;
        }
    }
    cout << dp[n][k] << endl;
    return 0;
}