UVA 1401 - Remember the Word(Trie+DP)
The DP word UVa Trie
2023-09-27 14:27:00 时间
UVA 1401 - Remember the Word
[题目链接]
题意:给定一些单词。和一个长串。问这个长串拆分成已有单词,能拆分成几种方式
思路:Trie,先把单词建成Trie。然后进行dp。dp[i]表示以i为开头的情况,然后每一个状态仅仅要在Trie树上找到对应的i开头的单词,然后dp[i] = sum{dp[i + len]}进行状态转移就可以
代码:
#include <cstdio> #include <cstring> const int MOD = 20071027; const int N = 300005; char str[N], word[105]; int S, sz; struct Node { int next[26], val; } node[N]; void insert(char *str) { int len = strlen(str); int u = 0; for (int i = 0; i < len; i++) { int v = str[i] - 'a'; if (node[u].next[v]) u = node[u].next[v]; else { node[u].next[v] = sz++; u = node[u].next[v]; node[u].val = 0; memset(node[u].next, 0, sizeof(node[u].next)); } } node[u].val = 1; } void init() { sz = 1; memset(node[0].next, 0, sizeof(node[0].next)); node[0].val = 0; } int dp[N]; void find(int i) { int u = 0; dp[i] = 0; for (int j = i; str[j]; j++) { int v = str[j] - 'a'; if (!node[u].next[v]) return; u = node[u].next[v]; if (node[u].val) dp[i] = (dp[i] + dp[j + 1]) % MOD; } } int main() { int cas = 0; while (~scanf("%s", str)) { scanf("%d", &S); init(); while (S--) { scanf("%s", word); insert(word); } int len = strlen(str); dp[len] = 1; for (int i = len - 1; i >= 0; i--) find(i); printf("Case %d: %d\n", ++cas, dp[0]); } return 0; }
相关文章
- Rust:error[E0468]: an `extern crate` loading macros must be at the crate root 处理方法
- UVa 825 Walking on the Safe Side(DP)
- Light OJ 1317 Throwing Balls into the Baskets 概率DP
- HDU4283:You Are the One(区间DP)
- open-falcon ---安装Dashboard时候报错"SSLError: The read operation timed out"
- [微软]The latest version of Windows is Windows Sandbox
- Mysql:Changes in MySQL 5.7.7 (2015-04-08, Release Candidate):The innodb_file_format default value was changed to Barracuda
- cdoj第13th校赛初赛H - Hug the princess
- [Flink] Flink作业报错:Caused by: The connector is trying to read binlog starting at GTIDs ..., but this is no longer available on the server[转载]
- POJ 3666 Making the Grade [DP]
- UVA1401 Remember the Word 字典树维护dp
- CodeForces833 B. The Bakery 线段树维护dp
- 【Hack The Box】linux练习-- Brainfuck
- The lexer hack
- MySQL: @variable vs. variable. Whats the difference?
- Zoj 3545 Rescue the Rabbit(ac自己主动机+dp)
- Harry Potter and the Prisoner of Azkaban
- HDU4251-The Famous ICPC Team Again(划分树)
- git clone 报错 “ gnutls_handshake() failed: The TLS connection was non-properly terminated.”
- 【POJ 3311】Hie with the Pie(状压DP)
- 单元测试报错 Error running xxx. Command line is too long. Shorten the command line via JAR manife
- XCODE 出现 The operation couldn't be completed.(LaunchServicesError error 0.)错误修复