Feng003

字符串

codeforces(2) DP(3) 图论(2) 基础数据结构(2) 数据结构课程(1) 概率期望(1) 算法课课程作业(4) 题解(6)

/ 注册

全部文章 / 字符串（共1篇）

破忒头的匿名信(AC自动机套dp)

题意：给你n个字符串，每个字符串s[i]都有相应的花费代价cost[i]。问用这些已有的串拼出一个给定的T串的最小花费是多少。思路：已知有n个模式串，再给出一个匹配串。很标准的一道AC自动机的题，花费最小的话也很容易想到用dp来做，dp[i]代表能拼出T[1~i]的最小花费,转移方程 dp[i]=...

DP AC自动机

2020-07-07

0 621