茂名专业做网站公司,wordpress英文版改成中文字体,mysql做wp网站,wordpress 慢途网主题(Remember the Word ,LA 3942) 题目来源#xff1a;https://vjudge.net/problem/UVALive-3942 题意#xff1a;给定一个字符串S以及n个单词#xff0c;字符用这n个单词进行拆分#xff0c;输出拆分的方案数。 思路#xff1a;dp字典树 可以先将这n个单词存储于字典树中https://vjudge.net/problem/UVALive-3942 题意给定一个字符串S以及n个单词字符用这n个单词进行拆分输出拆分的方案数。 思路dp字典树 可以先将这n个单词存储于字典树中并记dp[i]:字符i开始的字符串的分解方案数量(即后缀S[i...end]),则动态转移方程为dp[i]sum{dp[ilen(x)] | 单词x是S[i...end]的前缀}. 找S[i...end]的前缀可以在字典树中查找。 AC代码 #define _CRT_SECURE_NO_DEPRECATE
#includeiostream
#includecmath
#includealgorithm
#includecstring
#includevector
#includestring
#includeiomanip
#includemap
#includestack
#includeset
#includequeue
#includecstdio
using namespace std;
#define N_MAX 40005
#define L_MAX 4000*1005
#define INF 0x3f3f3f3f
#define MOD 20071027
typedef long long ll;
int n;
int dp[L_MAX];
int len[N_MAX];
char S[L_MAX];
struct Trie {int ch[L_MAX][26];int val[L_MAX];int sz;Trie() { sz 1; memset(ch[0], 0, sizeof(ch[0])); }void init() { sz 1; memset(ch[0], 0, sizeof(ch[0])); }int idx(char c) { return c - a; }void insert(char*s, int v) {int u 0, n strlen(s);for (int i 0; i n; i) {int c idx(s[i]);if (!ch[u][c]) {memset(ch[sz], 0, sizeof(ch[sz]));val[sz] 0;ch[u][c] sz;}u ch[u][c];}val[u] v;}//找长度为len的字符串s的前缀void find(char *s, int len, vectorintans) {int u 0;for (int i 0; i len; i) {if (s[i] \0)break;int c idx(s[i]);if (!ch[u][c]) break;u ch[u][c];if (val[u] ! 0)ans.push_back(val[u]);}}
};Trie trie;//不要放到main()下int main() {int Case 1;while (scanf(%s%d, S, n) !EOF) {memset(dp, 0, sizeof(dp));trie.init();for (int i 1; i n; i) {char x[100];scanf(%s, x);len[i] strlen(x);trie.insert(x, i);//将单词存入字典树,单词编号为i}int L strlen(S);dp[L] 1;for (int i L - 1; i 0; i--) {vectorintans;//存储单词的编号trie.find(S i, L - i, ans);for (int j 0; j ans.size(); j) {dp[i] (dp[i] dp[i len[ans[j]]]) % MOD;}}printf(Case %d: %d\n, Case, dp[0]);}return 0;
} 转载于:https://www.cnblogs.com/ZefengYao/p/8516576.html
