10.25

HDU 4117 

卡了很久的一个题目。比较综合。

看了很久题解还是各种写挫。

毕竟除了模拟题都没敲过那么长的。

 

题意：按顺序给N个单词，每个单词有权值，删去其中任意单词，使得前面的单词为后面单词的子串，求最大权值和。

做法：先建好AC自动机。

 

　　　最先想到的方法应该是这样的。

　　　定义dp[i]为以第i个串为最后一个串的答案。

　　　转移是dp[i]=max{W[i],dp[j]+W[i]}(j为i子串)

　　　那么只要再拿这N个单词在AC自动机上匹配一遍。

　　　每过一个节点相当于经过这个串的一个前缀。而这个节点的fail指向的是这个前缀的后缀。

　　　于是经过的每个节点时都通过fail一直走到root就遍历了这个串的所有子串。

　　　那么我们不妨定义f[u]为节点u所对应的单词的所有后缀的答案。

　　　那么可以用这种方法借助f[]来求出dp。

　　　

　　　然而这样是T的。

　　　于是考虑一种用线段树优化的方法。

　　　

　　　考虑到我们每次是顺着fail指针更新答案的。而且每次更新一个节点后只会影响fail指向它的节点。

　　　按照fail反向建树。这样每个父节点都是孩子节点的前缀。也就是每次更新一个节点后只影响它的子树。

　　　先在fail树上dfs一遍打好时间戳。

　　　线段树的每个节点维护时间戳所对应的fail树上节点的f[]值。

　　　于是按照段更新的区间最值线段树写就可以了。

　　　每次询问所有前缀的f[]。再更新末节点对应子树的f[]。

　　　所有取最大即为答案。

　　　

　　　最后防爆栈黑科技交C++。　　　

 

1 #pragma comment(linker, "/STACK:102400000,102400000")  2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
             7 using namespace std;  8 const int maxnode=3e5+10,sigma_size=26;  9 const int maxn=2e4+10; 10 int n,p[maxn],W[maxn]; 11 char s[maxnode]; 12  13 //fail_tree 14 int cnt,headlist[maxnode]; 15 int timer,dfn[maxnode][2]; 16 struct e 17 { 18     int to,pre; 19 } edge[2*maxnode]; 20  21 void add(int from,int to) 22 { 23     cnt++; 24     edge[cnt].pre=headlist[from]; 25     edge[cnt].to=to; 26     headlist[from]=cnt; 27 } 28  29 void dfs(int pos,int fa) 30 { 31     dfn[pos][0]=++timer; 32     for(int i=headlist[pos];i;i=edge[i].pre) 33     { 34         int to=edge[i].to; 35         if(to==fa) continue; 36         dfs(to,pos); 37     } 38     dfn[pos][1]=++timer; 39 } 40  41 //seg_tree 42 struct seg_tree 43 { 44     int l,r,val; 45 }tree[maxnode<<3]; 46  47 void buildtree(int pos,int l,int r) 48 { 49     tree[pos].l=l; 50     tree[pos].r=r; 51     tree[pos].val=0; 52     if(l
           
            =l&&tree[pos].r<=r) tree[pos].val=max(tree[pos].val,val); 68 else 69 { 70 pushdown(pos); 71 if((tree[pos].l+tree[pos].r)/2>=r) update(pos*2,l,r,val); 72 else if((tree[pos].l+tree[pos].r)/2
            
             =l&&tree[pos].r<=r) return tree[pos].val; 84 int ret=0; 85 pushdown(pos); 86 if((tree[pos].l+tree[pos].r)/2>=r) ret=max(ret,query(pos*2,l,r)); 87 else if((tree[pos].l+tree[pos].r)/2
             

q;123 fail[0]=0;124 for(int i=0;i