洛谷 P1481 分析（别看）

科技起源

2026-07-17 14:37:16

发布于：河北

0阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最大值

1.2 题目背景、允许、禁止与限制

背景：有 $n$ 个字符串
允许：从中选出若干个字符串组成一个字符串序列，求序列最长长度
禁止：
限制：选出的序列中第 $i(1 \le i < 序列长度)$ 个字符串一定是第 $i+1$ 个字符串的前缀

1.3 题目数据范围与猜测

$1 \le n \le 2000 \longrightarrow O(n^2)$

1.4 一句话概括题意

有一些字符串，从中选出若干个字符串，求满足条件的情况下序列的最长长度。

2 题目破题推导

字符串 $s_1$ 是 $s_2$ 的前缀， $s_2$ 的长度一定 $\ge s_1$ 的长度，并且 $s_1=s_2[0,len(s_1)]$

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：动态求取最大值 $\longrightarrow$ $\huge{线性dp}$
关键词：快速匹配某几位 $\longrightarrow$ $\huge{字符串hash}$

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const ull base = 131;
const ull mod = 1000000007ULL;
const int N = 2222, M = 77;

ull h[N][M]; // 二维哈希：h[i][j] 第i个单词前j个字符的哈希
string s[N];    // 记录每个字符串是啥 
int len[N];     // 记录每个单词长度
int dp[N];      // dp[i] 以第i个单词结尾的最长前缀链长度
ull getHash(const string &s) {
    ull res = 0;
    for (char c : s){
    	res = (res * base + c) % mod;
	}
	return res; 
}

int main() {
	
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        len[i] = s[i].size();
        string pre;
        for (int j = 1; j <= len[i]; j++) {
            pre += s[i][j - 1];// 拼接 
            h[i][j] = getHash(pre);
        }
    }
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
	}
	for (int i = 1;i <= n;i++){
        for (int k = 1; k < i; k++) {
            if (len[k] >= len[i]) continue; // 更长一定不是前缀（防止这种情况的发生） 
            // 哈希相等代表是前缀
            if (h[k][len[k]] == h[i][len[k]]) {
                dp[i] = max(dp[i], dp[k] + 1);
            }
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;i++){
    	ans = max(ans, dp[i]);
	}
    cout << ans << endl;
    return 0;
}