[关闭]
@Jerusalem 2015-11-13T08:34:37.000000Z 字数 3427 阅读 1234

HDU2296



傻逼DP,求出深搜序,线段树优化即可。

实在不明白为什么爆内存……先放着,有空再改。



  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <iostream>
  7. #include <queue>
  8. #include <vector>
  9. using namespace std;
  10. const int maxnode=300005,sigma=26,maxn=20005;
  11. queue<int> Q;
  12. vector<int> G[maxnode];
  13. int num[maxnode];
  14. string S[maxn];
  15. int w[maxn];
  16. int f[maxn];
  17. struct Node{
  18. int ls,rs;
  19. int w;
  20. int Lazy;
  21. Node(){
  22. ls=rs=0;
  23. w=0;
  24. Lazy=0;
  25. }
  26. void Clear(){
  27. ls=rs=0;
  28. w=0;
  29. Lazy=0;
  30. }
  31. };
  32. struct Segement_Tree{
  33. Node tree[maxnode*4];
  34. int root,num;
  35. Segement_Tree(){
  36. root=num=0;
  37. }
  38. void Clear(){
  39. root=num=0;
  40. }
  41. void MakeTree(int& root,int l,int r){
  42. root=++num;
  43. tree[root].Clear();
  44. if(l==r)
  45. return;
  46. int mid=(l+r)/2;
  47. MakeTree(tree[root].ls,l,mid);
  48. MakeTree(tree[root].rs,mid+1,r);
  49. }
  50. void PushDown(int root){
  51. tree[tree[root].ls].Lazy=max(tree[tree[root].ls].Lazy,tree[root].Lazy);
  52. tree[tree[root].rs].Lazy=max(tree[tree[root].rs].Lazy,tree[root].Lazy);
  53. tree[root].Lazy=0;
  54. }
  55. void Maintain(int root){
  56. tree[root].w=max(tree[root].Lazy,max(tree[tree[root].ls].w,tree[tree[root].rs].w));
  57. }
  58. void Update(int root,int l,int r,int y1,int y2,int Set){
  59. if(y1<=l&&r<=y2){
  60. tree[root].Lazy=max(tree[root].Lazy,Set);
  61. }
  62. else{
  63. PushDown(root);
  64. int mid=(l+r)/2;
  65. if(y1<=mid)
  66. Update(tree[root].ls,l,mid,y1,y2,Set);
  67. else
  68. Maintain(tree[root].ls);
  69. if(mid<y2)
  70. Update(tree[root].rs,mid+1,r,y1,y2,Set);
  71. else
  72. Maintain(tree[root].rs);
  73. }
  74. Maintain(root);
  75. }
  76. int Query(int root,int l,int r,int y1,int y2){
  77. if(y1<=l&&r<=y2)
  78. return tree[root].w;
  79. int mid=(l+r)/2;
  80. PushDown(root);
  81. Maintain(tree[root].ls);
  82. Maintain(tree[root].rs);
  83. int ans=0;
  84. if(y1<=mid)
  85. ans=max(ans,Query(tree[root].ls,l,mid,y1,y2));
  86. if(mid<y2)
  87. ans=max(ans,Query(tree[root].rs,mid+1,r,y1,y2));
  88. return ans;
  89. }
  90. };
  91. struct Trie{
  92. int tot;
  93. int num;
  94. int ch[maxnode][sigma];
  95. int f[maxnode];
  96. vector<int> G[maxnode];
  97. int l[maxnode];
  98. int r[maxnode];
  99. bool val[maxnode];
  100. Trie(){
  101. tot=1;
  102. num=0;
  103. memset(ch,0,sizeof(ch));
  104. memset(f,0,sizeof(f));
  105. memset(val,false,sizeof(val));
  106. }
  107. void Clear(){
  108. tot=1;
  109. num=0;
  110. memset(ch[0],0,sizeof(ch[0]));
  111. memset(val,false,sizeof(val));
  112. for(int i=0;i<maxnode;i++)
  113. G[i].clear();
  114. }
  115. int newnode(){
  116. memset(ch[tot],0,sizeof(ch[tot]));
  117. return tot++;
  118. }
  119. int idx(char a){
  120. return a-'a';
  121. }
  122. void Insert(string s){
  123. int len=s.length();
  124. int u=0;
  125. for(int i=0;i<len;i++){
  126. if(!ch[u][idx(s[i])])
  127. ch[u][idx(s[i])]=newnode();
  128. u=ch[u][idx(s[i])];
  129. }
  130. val[u]=true;
  131. }
  132. void GetLine(int u){
  133. l[u]=num;
  134. for(int i=0;i<G[u].size();i++){
  135. int v=G[u][i];
  136. num++;
  137. GetLine(v);
  138. }
  139. r[u]=++num;
  140. }
  141. void Build(){
  142. while(!Q.empty())
  143. Q.pop();
  144. for(int i=0;i<sigma;i++)
  145. if(ch[0][i]){
  146. f[ch[0][i]]=0;
  147. Q.push(ch[0][i]);
  148. G[0].push_back(ch[0][i]);
  149. }
  150. while(!Q.empty()){
  151. int u=Q.front();
  152. Q.pop();
  153. for(int i=0;i<sigma;i++){
  154. if(!ch[u][i])
  155. continue;
  156. int v=ch[u][i],r=f[u];
  157. while(r&&!ch[r][i])
  158. r=f[r];
  159. Q.push(v);
  160. f[v]=ch[r][i];
  161. G[f[v]].push_back(v);
  162. }
  163. }
  164. GetLine(0);
  165. }
  166. };
  167. Trie Aho_Corasick;
  168. Segement_Tree DfsOrder;
  169. int n,T;
  170. void Solve()
  171. {
  172. for(int k=1;k<=T;k++){
  173. cin>>n;
  174. Aho_Corasick.Clear();
  175. memset(num,0,sizeof(num));
  176. for(int i=1;i<=n;i++){
  177. cin>>S[i]>>w[i];
  178. Aho_Corasick.Insert(S[i]);
  179. }
  180. int ans=0;
  181. DfsOrder.Clear();
  182. Aho_Corasick.Build();
  183. int l=0,r=Aho_Corasick.num;
  184. DfsOrder.MakeTree(DfsOrder.root,l,r);
  185. for(int i=1;i<=n;i++){
  186. int len=S[i].length();
  187. int u=0;
  188. int tmp=0;
  189. for(int j=0;j<len;j++){
  190. u=Aho_Corasick.ch[u][S[i][j]-'a'];
  191. tmp=max(tmp,DfsOrder.Query(DfsOrder.root,l,r,Aho_Corasick.l[u],Aho_Corasick.l[u])+w[i]);
  192. }
  193. DfsOrder.Update(DfsOrder.root,l,r,Aho_Corasick.l[u],Aho_Corasick.r[u],tmp);
  194. ans=max(ans,tmp);
  195. }
  196. printf("Case #%d: %d\n",k,ans);
  197. }
  198. }
  199. void ReadData()
  200. {
  201. freopen("4117.in","r",stdin);
  202. freopen("4117.out","w",stdout);
  203. ios::sync_with_stdio(false);
  204. cin>>T;
  205. }
  206. void Close()
  207. {
  208. fclose(stdin);
  209. fclose(stdout);
  210. }
  211. int main()
  212. {
  213. ReadData();
  214. Solve();
  215. Close();
  216. return 0;
  217. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注